## Saturday, November 15, 2014

### [LeetCode] 3Sum

Given an array S of n integers, are there elements abc 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)```

(1, 2, 3, 4), target = 6

(1, 2, 2, 2, 3, 4), target = 9

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36``` ```class Solution { public: vector > threeSum(vector &num) { return threeSumGen(num, 0); } vector > threeSumGen(vector &num, int target) { vector> allSol; if(num.size()<3) return allSol; sort(num.begin(),num.end()); for(int i=0; i0 && num[i]==num[i-1]) continue; int left=i+1, right=num.size()-1; while(left sol; sol.push_back(num[i]); sol.push_back(num[left]); sol.push_back(num[right]); allSol.push_back(sol); left++; right--; while(num[left]==num[left-1]) left++; while(num[right]==num[right+1]) right--; } else if(curSum