The coding questions in sum related can be summarized as: 1) 2Sum, 2) 3Sum, 3) 3SumClosest, 4) 4Sum.
1. 2Sum
Given an array of integers, find two numbers such that they add up to a specific target number.
The function twoSum should return indices of the two numbers such that they
add up to the target,
where index1 must be less than index2. Please note
that your returned answers (both index1 and index2) are not zero-based.
You may assume that each input would have exactly one solution.
Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2
Solution: 1. Sort first. O(nlgn); 2. Hash table. O(n)
1 bool compare(const pair<int, int> &a, const pair<int, int> &b) { 2 return a.first < b.first; 3 } 4 5 class Solution { 6 public: 7 vector<int> twoSum(vector<int> &numbers, int target) { 8 return twoSum_1(numbers, target); 9 } 10 11 vector<int> twoSum_1(vector<int> &numbers, int target) { // pair<val,index> 12 vector<pair<int, int> > nums(numbers.size()); 13 for (int i = 0; i < numbers.size(); ++i) 14 nums[i] = make_pair(numbers[i], i+1); 15 sort(nums.begin(), nums.end(), compare); 16 17 int l = 0, r = nums.size() - 1; 18 while (l < r) { 19 int sum = nums[l].first + nums[r].first; 20 if (sum == target) break; 21 else if (sum < target) l++; 22 else r--; 23 } 24 25 vector<int> res; 26 res.push_back(min(nums[l].second, nums[r].second)); 27 res.push_back(max(nums[l].second, nums[r].second)); 28 return res; 29 } 30 31 vector<int> twoSum_2(vector<int> &numbers, int target) { // hash-table 32 unordered_map<int, int> map; 33 for (int i = 0; i < numbers.size(); ++i) 34 map[numbers[i]] = i + 1; 35 for (int i = 0; i < numbers.size(); ++i) { 36 unordered_map<int, int>::iterator it = map.find(target - numbers[i]); 37 if (it == map.end()) continue; 38 vector<int> res; 39 res.push_back(min(i+1, it->second)); 40 res.push_back(max(i+1, it->second)); 41 return res; 42 } 43 } 44 };
2. 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.
Note:
Elements in a triplet (a,b,c) must be in non-descending
order. (ie, a <= b <= c)
The solution set must not contain duplicate
triplets.
For example, given array S = {-1 0 1 2 -1 -4},
A solution set
is:
(-1, 0, 1)
(-1, -1, 2)
1 class Solution { 2 public: 3 vector<vector<int> > threeSum(vector<int> &num) { 4 vector<vector<int> > res; 5 if(num.size() < 3) 6 return res; 7 sort(num.begin(), num.end()); 8 int N = num.size(); 9 for(int i = N-1; i >= 2; i--) { 10 if(i != N-1 && num[i] == num[i+1]) { 11 continue; } // handle duplicated cases 12 for(int j = 0, k = i-1; j < k; ) { 13 if(j != 0 && num[j] == num[j-1]) { j++; continue; } 14 if(k != i-1 && num[k] == num[k+1]) { k--; continue; } 15 int sum = num[i] + num[j] + num[k]; 16 if(sum == 0) { 17 vector<int> tmp(3); 18 tmp[0] = num[j]; 19 tmp[1] = num[k]; 20 tmp[2] = num[i]; 21 res.push_back(tmp); 22 j++; 23 k--; 24 } 25 else if(sum < 0) { j++; } 26 else { k--; } 27 } 28 } 29 return res; 30 } 31 };
3. 3SumClosest
Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers.
You may assume that each input would have exactly one solution.
For example, given
array S = {-1 2 1 -4}, and target = 1.
The sum that is closest to the target
is 2. (-1 + 2 + 1 = 2).
1 class Solution { 2 public: 3 int threeSumClosest(vector<int> &num, int target) { 4 if(num.size() < 3) { 5 return INT_MAX; 6 } 7 sort(num.begin(), num.end()); 8 int N = num.size(); 9 int diff = INT_MAX; 10 int res = INT_MAX; 11 for(int k = N-1; k >= 2; k--) { 12 if(k != N-1 && num[k] == num[k+1]) 13 continue; 14 int i = 0, j = k-1; 15 while(i < j) { 16 if(i != 0 && num[i] == num[i-1]) { i++; continue; } 17 if(j != k-1 && num[j] == num[j+1]) { j--; continue; } 18 int sum = num[i] + num[j] + num[k]; 19 if(sum == target) return sum; 20 else if(sum < target) i++; 21 else j--; 22 if(abs(sum-target) < diff) { 23 diff = abs(sum-target); 24 res = sum; 25 } 26 } 27 } 28 return res; 29 } 30 };
4. 4Sum
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.
Note:
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.
Note:
Elements in a quadruplet
(a,b,c,d) must be in non-descending order. (ie, a <= b <= c <= d)
The solution set must not contain duplicate quadruplets.
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)
1 class Solution { 2 public: 3 vector<vector<int> > fourSum(vector<int> &num, int target) { 4 vector<vector<int> > res; 5 if(num.size() < 4) { 6 return res; 7 } 8 int N = num.size(); 9 sort(num.begin(), num.end()); 10 for(int i = N-1; i >= 3; i--) { 11 if(i != N-1 && num[i] == num[i+1]) 12 continue; 13 for(int j = i-1; j >= 2; j--) { 14 if(j != i-1 && num[j] == num[j+1]) 15 continue; 16 int l = 0, r = j-1; 17 while(l < r) { 18 if(l != 0 && num[l] == num[l-1]) { l++; continue; } 19 if(r != j-1 && num[r] == num[r+1]) { r--; continue; } 20 int sum = num[i] + num[j] + num[l] + num[r]; 21 if(sum == target) { 22 vector<int> tmp(4); 23 tmp[0] = num[l]; 24 tmp[1] = num[r]; 25 tmp[2] = num[j]; 26 tmp[3] = num[i]; 27 res.push_back(tmp); 28 l++; 29 r--; 30 } 31 else if(sum < target) { l++; } 32 else { r--; } 33 } 34 } 35 } 36 return res; 37 } 38 };
Leetcode个人总结1 Sum问题(4),布布扣,bubuko.com
原文：http://www.cnblogs.com/zhengjiankang/p/3595483.html