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:
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)
跟3Sum一样，先用两层循环，注意去重。
1 class Solution { 2 public: 3 vector<vector<int> > fourSum(vector<int> &num, int target) { 4 vector<vector<int> > res; 5 vector<int> v(4); 6 int sum; 7 if (num.size() < 4) return res; 8 sort(num.begin(), num.end()); 9 for (int i = 0; i < num.size() - 3; ++i) { 10 if (i > 0 && num[i] == num[i-1]) 11 continue; 12 for (int j = i + 1; j < num.size() - 2; ++j) { 13 if (j > i + 1 && num[j] == num[j-1]) 14 continue; 15 int low = j + 1, high = num.size() - 1; 16 while (low < high) { 17 sum = num[i] + num[j] + num[low] + num[high]; 18 if (sum > target) { 19 --high; 20 } else if (sum < target) { 21 ++low; 22 } else { 23 v[0] = num[i]; 24 v[1] = num[j]; 25 v[2] = num[low]; 26 v[3] = num[high]; 27 res.push_back(v); 28 while (low < num.size() && num[low+1] == num[low]) ++low; 29 while (high > 0 && num[high-1] == num[high]) --high; 30 ++low; --high; 31 } 32 } 33 } 34 } 35 return res; 36 } 37 };
[Leetcode] 4Sum,布布扣,bubuko.com
原文：http://www.cnblogs.com/easonliu/p/3694667.html