Problem:
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)
Analysis:
It's very much like 2 sum problem.
First need to sort the given array, then pick every different element n in the sorted array, do the following:
1. set two pointers i and j, i points to the next position of n, j points to the lasted element of array
2. get the sum of a[i], a[j], a[n]: if sum == 0, find a solution; if sum > 0, we decrease j by 1; if sum < 0, we increase i by 1; repeat until i > j;
3. after find a solution, we need to update i and j, due to the repeatness of the element, we must find the next element that is different from the current one.
4. update the element n also requires a different new element.
Code:
1 class Solution { 2 public: 3 vector<vector<int> > threeSum(vector<int> &num) { 4 // Start typing your C/C++ solution below 5 // DO NOT write int main() 6 vector<vector<int> > r; 7 sort(num.begin(), num.end()); 8 9 int n = 0; 10 while (n < num.size()) { 11 int i = n+1, j = num.size()-1; 12 while (i < j) { 13 int sum = num[i] + num[j] + num[n]; 14 15 if (sum == 0) { 16 vector<int> res; 17 res.push_back(num[n]); 18 res.push_back(num[i]); 19 res.push_back(num[j]); 20 r.push_back(res); 21 22 do {i++;} while(num[i-1] == num[i] && i<num.size()); 23 do {j--;} while(num[j] == num[j+1] && j>n); 24 25 } else if (sum > 0) { 26 j--; 27 } else if (sum < 0) { 28 i++; 29 } 30 } 31 32 n++; 33 while (num[n] == num[n-1] && n < num.size()) n++; 34 35 if (n == num.size()) 36 break; 37 } 38 39 return r; 40 } 41 };
Attention: