首页 > 代码库 > 1. Two Sum&&15. 3Sum&&18. 4Sum
1. Two Sum&&15. 3Sum&&18. 4Sum
题目:
1. Two Sum
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Given nums = [2, 7, 11, 15], target = 9, Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1].
15.3Sum:
Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
For example, given array S = [-1, 0, 1, 2, -1, -4], A solution set is: [ [-1, 0, 1], [-1, -1, 2] ]
18. 4Sum
Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.
For example, given array S = [1, 0, -1, 0, -2, 2], and target = 0. A solution set is: [ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ]
思路:
这三道题本质上属于同一问题:给定一个数组和目标target,求k个元素,使得k个元素相加的和为target。可能出现的变式为:1.求元素的下标;2.不得重复使用同一元素等,下面进行分析。
对于2Sum而言,要求a+b=target,也就是任意选定元素a,寻找数组中是否有元素b使得b=target-a。可以选择方法有:
方法一:枚举所有的2-subset, 那么这样的复杂度就是从N选出2个,复杂度是O(N^2)
方法二:对数组进行排序并利用头尾两个指针找到两个数使得他们的和等于target。
对于3Sum而言,要求a+b+c=target,这道题可以转化为2Sum问题。即任意选定元素a,在剩余的元素中查找是否存在2个数使得b+c=targe-a。
对于4Sum而言,也可以转化为2Sum问题。任意选定元素a和b,在剩余的元素中查找是否存在2个数使得c+d=targe-a-b。
代码:
2Sum:
1 class Solution { 2 public: 3 vector<int> twoSum(vector<int>& nums, int target) { 4 int l = 0; 5 int r = nums.size() - 1; 6 int i = 0; 7 vector<int> result; 8 multimap<int, int> m; 9 multimap<int, int>::iterator itmulti; 10 for (vector<int>::iterator it = nums.begin(); it != nums.end(); it++) { 11 int temp = *it; 12 m.insert(make_pair(temp, i++)); 13 } 14 sort(nums.begin(), nums.end()); 15 while (l < r) { 16 if (nums[l] + nums[r] == target) { 17 if (nums[l] == nums[r]) { 18 for (itmulti = m.equal_range(nums[l]).first; 19 itmulti != m.equal_range(nums[l]).second; 20 itmulti++) { 21 result.push_back((*itmulti).second); 22 } 23 } else { 24 itmulti = m.equal_range(nums[l]).first; 25 result.push_back((*itmulti).second); 26 itmulti = m.equal_range(nums[r]).first; 27 result.push_back((*itmulti).second); 28 } 29 break; 30 } else if (nums[l] + nums[r] < target) { 31 l++; 32 } else { 33 r--; 34 } 35 } 36 return result; 37 } 38 };
3Sum:
1 class Solution { 2 public: 3 vector<vector<int> > threeSum(vector<int>& nums) { 4 sort(nums.begin(), nums.end()); 5 vector<vector<int> > results; 6 for (int i = 0; i < (signed) nums.size() - 2; i++) { 7 if (i > 0 && nums[i] == nums[i - 1]) 8 continue; 9 10 int l = i + 1; 11 int r = nums.size() - 1; 12 while (l < r) { 13 if (nums[l] + nums[r] + nums[i] < 0) { 14 l++; 15 } else if (nums[l] + nums[r] + nums[i] > 0) { 16 r--; 17 } else { 18 vector<int> result; 19 result.push_back(nums[i]); 20 result.push_back(nums[l]); 21 result.push_back(nums[r]); 22 results.push_back(result); 23 while (l < r && nums[l] == nums[l + 1]) { 24 l++; 25 } 26 while (l < r && nums[r] == nums[r - 1]) { 27 r--; 28 } 29 l++; 30 r--; 31 } 32 } 33 } 34 return results; 35 } 36 };
4Sum:
1 class Solution { 2 public: 3 vector<int> twoSum(vector<int>& nums, int target) { 4 int l = 0; 5 int r = nums.size() - 1; 6 int i = 0; 7 vector<int> result; 8 multimap<int, int> m; 9 multimap<int, int>::iterator itmulti; 10 for (vector<int>::iterator it = nums.begin(); it != nums.end(); it++) { 11 int temp = *it; 12 m.insert(make_pair(temp, i++)); 13 } 14 sort(nums.begin(), nums.end()); 15 while (l < r) { 16 if (nums[l] + nums[r] == target) { 17 if (nums[l] == nums[r]) { 18 for (itmulti = m.equal_range(nums[l]).first; 19 itmulti != m.equal_range(nums[l]).second; 20 itmulti++) { 21 result.push_back((*itmulti).second); 22 } 23 } else { 24 itmulti = m.equal_range(nums[l]).first; 25 result.push_back((*itmulti).second); 26 itmulti = m.equal_range(nums[r]).first; 27 result.push_back((*itmulti).second); 28 } 29 break; 30 } else if (nums[l] + nums[r] < target) { 31 l++; 32 } else { 33 r--; 34 } 35 } 36 return result; 37 } 38 };
1. Two Sum&&15. 3Sum&&18. 4Sum