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 };
原文：http://www.cnblogs.com/zhengjiankang/p/3644641.html