## Friday, January 25, 2013

### [LeetCode] 3 Sum, Solution

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)
```
» 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].