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)
Answer:
Similar to "2 Sum", sort the array firstly, a + b + c = t, choose (a) from array every time, then find from the left right elements for b and c whose sum to be (t-a), using two pointer method here.
Note: there exists duplicate elements in the array, so we need to avoid duplicate triplets in the solution result!
vector<vector<int> > threeSum(vector<int> &num) {
sort(num.begin(), num.end());
vector<vector<int> > triplets;
vector<int> triplet(3,INT_MIN);
for (int i = 0;i < num.size(); i++) {
if(i>0 && num[i]==num[i-1]) continue; // To avoid duplicate triplets!
int j = i + 1;
int k = num.size() - 1;
while (j < k) {
if (num[i] + num[j] + num[k] < 0) {
j++;
} else if (num[i] + num[j] + num[k] > 0) {
k--;
} else {
if(num[j]!=triplet[1] || num[k]!=triplet[2]){ // To avoid duplicate triplets!
triplet[0] = num[i];
triplet[1] = num[j];
triplet[2] = num[k];
triplets.push_back(triplet);
}
j++;
k--;
}
}
}
return triplets;
}
No comments:
Post a Comment