3sum (C++ code)

LeetCode 3Sum Jan 18 '12
难度3，出现频率5

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) 

思路： 固定第一个元素，另外两个元素由sliding window决定。如何去掉重复元素？

1，第一层循环跳过重复的；

2，第二层循环从两头跳过循环的；

时间复杂度O(n^2) 

 
 vector< vector<int> > threeSum(vector<int> &num){
  
  int n = num.size(); 
  vector< vector<int> > res;
  vector<int> cur;
  
  sort(num.begin(), num.end());

  for(int i = 0; i < n-2; i++){
      if(i > 0 && num[i] == num[i-1]) continue;
      cur.push_back(num[i]);
      int start = i + 1, end = n - 1; 
      while(start < end){
                  if(start > i+1 && num[start] == num[start-1]) {
                           start++; continue;
                           }
                  if(end < n-1 && num[end] == num[end+1]){
                           end--; continue;
                         }
                  int sum = num[i] + num[start] + num[end];
                  if(sum == 0) {
                         cur.push_back(num[start]);
                         cur.push_back(num[end]);
                         res.push_back(cur);
                         cur.resize(1);                        
                         start++;
                         end--;
                         }
                  else if(sum > 0) end--;
                  else start++;
                  }  
      cur.pop_back();
  }
  
 return res;

}