[M]Leetcode15-3sum

分析

1.暴力搜
2.类似两数和的思想
a+b+c=0 ->a=-(b+c)
如果a确定的话就和两数和是一样的思路。
这里采用双指针，从两边往中间搜：

其实这题相比2SUM多了几个难点：

1. 数组里允许重复的数
2. 结果要按升序排列
3. 结果中不能出现重复的结果

a+b+c=0也就是说一定要有一项是负的，为了降低复杂度和最后结果升序，我们现将数组排序，a始终指向负数且是最小的。
b从a后开始搜。
c则从最右往中间搜。

可以想到伪代码：

sort()
for(int a=0;a<len-2;a++){
  b=a+1

  while(b<c){
   if(b+c<-a) b往右走
   if(b+c>-a) c往左走
  else 符合条件，存入vector
  }
}

但是！！！
不能是重复的数组，也就是说还需要排除相同的情况！
只要判断a,b,c指向的数是否判断过，判断过的话就跳过即可。

sort()
for(int a=0;a<len-2;a++){
  b=a+1
 if(a<len-2&&a==a-1) continue
  while(b<c){
   if(b+c<-a) b++
   if(b+c>-a) c--
  else
     符合条件，存入vector
    b++ c--
      if(b<c&&b==b-1) b++
      if(b<c&&c==c+1) c--
  }
}

代码（C++）

vector<vector<int> > threeSum(vector<int>& nums) {
    
    vector< vector<int> > ret;
    int len=nums.size();
    sort(nums.begin(), nums.end());  
    for(int left=0;left<len-2;left++){ 
        int mid=left+1;
        int right=len-1;
        int tmp=0-nums[left];
        
        if (nums[left] > 0) break;
        if(nums[left]==nums[left-1]){
                continue;
            }
        while(mid<right){
            
            if(nums[mid]+nums[right]<tmp){
                mid++;
            }else if(nums[mid]+nums[right]>tmp){
                right--;
            }else{
                ret.push_back({nums[left],nums[mid],nums[right]});
                mid++;
                right--;
                //跳过重复的部分
                while(mid<right&&nums[mid]==nums[mid-1]){
                    mid++;
                } 
                while(mid<right&&nums[right]==nums[right+1]){
                    right--;
                }
            }
            
        }
        
    }
    
    return ret;
}

参考资料：https://hk029.gitbooks.io/leetbook/content/%E6%95%B0%E7%BB%84/015.%203Sum/015.%203Sum.html
http://www.cnblogs.com/grandyang/p/4481576.html