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)» Solve this problem
[Thoughts]
Two-pointer scan.
[Code]
1: vector<vector<int> > threeSum(vector<int> &num) { 2: // Start typing your C/C++ solution below 3: // DO NOT write int main() function 4: std::sort(num.begin(), num.end()); 5: vector<vector<int> > result; 6: int len = num.size(); 7: for(int i =0; i< len; i++) 8: { 9: int target = 0-num[i]; 10: int start = i+1, end =len-1; 11: while(start<end) 12: { 13: if(num[start] + num[end] == target) 14: { 15: vector<int> solution; 16: solution.push_back(num[i]); 17: solution.push_back(num[start]); 18: solution.push_back(num[end]); 19: result.push_back(solution); 20: start++; end--; 21:
while(start<end && num[start] == num[start-1]) start++;
22:
while(start<end && num[end] == num[end+1]) end--;
23: } 24: else if(num[start] + num[end] < target) 25: { 26: start++; 27: } 28: else 29: { 30: end--; 31: } 32: } 33: if(i<len-1) 34: { 35:
while(num[i] == num[i+1]) i++;
36: } 37: } 38: return result; 39: }
[Some tricks]
1. Line 21 and Line 22.
filter the duplicate during two-pointer scan. For example [-2, 0, 0, 2,2], the expected output should be [-2,0,2]. If no filter here, the output will be duplicate as [-2,0,2] and [-2,0,2]
2. Line 35
filter the duplicate for outside iteration. For example [-2, -2, -2, 0,2].
No comments:
Post a Comment