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)
无聊 3sum 的变形
class Solution {
public:
vector<vector<int> > fourSum(vector<int> &num, int target) {
// Note: The Solution object is instantiated only once and is reused by each test case.
vector<vector<int>> res;
int len = num.size();
if(len < ) return res;
sort(num.begin(),num.end());
for(int i = ; i< len-;++i){
while(i> && i< len- && num[i] == num[i-])++i;
for(int j = i+; j< len-; ++j){
while(j!=i+ && j< len-&&num[j] == num[j-])++j;
int left = j+;
int right = len-;
while(left < right){
int sum = num[i] + num[j] +num[left]+num[right];
if(sum == target){
vector<int> ans;
ans.push_back(num[i]);
ans.push_back(num[j]);
ans.push_back(num[left]);
ans.push_back(num[right]);
res.push_back(ans);
left++;
while(left<right && num[left]==num[left-]) ++left;
right--;
while(left < right && num[right] == num[right+]) --right;
}else if(sum <target){
left++;
while(left<right && num[left]==num[left-]) ++left;
}else{
right--;
while(left < right && num[right] == num[right+]) --right;
}
}//while(left <right)
}//for j
}// for i
return res;
}
};