4 Sum(C++実装)
1895 ワード
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.
微信の公衆番号に注目してください.コンピュータの視覚です.
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)
class Solution {
public:
vector<vector<int> > fourSum(vector<int> &num, int target) {
vector<vector<int> > ret;
sort(num.begin(), num.end());
for(int i = 0; i < num.size(); ++i) {
if(i > 0 && num[i] == num[i-1]) continue;
for(int j = i + 1; j < num.size(); ++j) {
if(j > i+1 && num[j] == num[j-1]) continue;
int k = j + 1, l = num.size() - 1;
int tsum = target - num[i] - num[j];
while(k < l) {
int t = num[k] + num[l];
if (t > tsum) {--l;}
else if (t < tsum) {++k;}
else {
vector<int> vec({num[i], num[j], num[k], num[l]});
ret.push_back(vec);
while(num[++k] == num[k-1]);
while(num[--l] == num[l+1]);
}
}
}
}
return ret;
}
};
微信の公衆番号に注目してください.コンピュータの視覚です.