分析

1.暴力搜
2.類似兩數(shù)和的思想
a+b+c=0 ->a=-(b+c)
如果a確定的話就和兩數(shù)和是一樣的思路。
這里采用雙指針，從兩邊往中間搜：

其實這題相比2SUM多了幾個難點：

1. 數(shù)組里允許重復的數(shù)
2. 結果要按升序排列
3. 結果中不能出現(xiàn)重復的結果

a+b+c=0也就是說一定要有一項是負的，為了降低復雜度和最后結果升序，我們現(xiàn)將數(shù)組排序，a始終指向負數(shù)且是最小的。
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
  }
}

但是?。?！
不能是重復的數(shù)組，也就是說還需要排除相同的情況！
只要判斷a,b,c指向的數(shù)是否判斷過，判斷過的話就跳過即可。

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