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) 超时的做法，先将其排序，一个指针指向队首，一个指向队尾，另一个指针在中间，不断移动指针，看其是否能够满足条件。

public static List
      
       
        > threeSum(int[] nums) {           Arrays.sort(nums);            List
        
         
          > ans=new ArrayList
          
           
            >(); int m=nums.length; if(m<3) return ans; int l=0; int a=0; int num0=0; while(a
            
              temp=new ArrayList
             
              (); temp.add(nums[0]); temp.add(nums[0]); temp.add(nums[0]); ans.add(temp); } return ans; } int i=0; int k; System.out.println(l); while(i
              
               =1){ if(nums[i]==nums[i-1]){ i++; continue; } } int j=m-1; while(j>l){ if(j
               
                 temp=new ArrayList
                
                 (); temp.add(nums[i]); temp.add(nums[k]); temp.add(nums[j]); ans.add(temp); } } if(nums[k]==nums[j]){ if(nums[i]+nums[j]+nums[k]==0){ List
                 
                   temp=new ArrayList
                  
                   (); temp.add(nums[i]); temp.add(nums[k]); temp.add(nums[j]); ans.add(temp); } break; } if(nums[k]==nums[k-1]){ k++; continue; } if(nums[i]+nums[j]+nums[k]==0){ List
                   
                     temp=new ArrayList
                    
                     (); temp.add(nums[i]); temp.add(nums[k]); temp.add(nums[j]); ans.add(temp); } if(nums[i]+nums[j]+nums[k]>0){ break; } System.out.println(i+" "+j+" "+k); k++; /*if(!(i
                     
                    
                   
                  
                 
                
               
              
             
            
           
          
         
        
       
      

 在去重方面做的不够好，代码写得很臃肿。一个更好一点的做法。

public class Solution {     void InsertSort(int[] a, int n)      {          int temp;          for (int i = 1; i < n; ++i)          {              temp = a[i];              int j;              for (j = i; j > 0 && temp < a[j-1]; --j)              {                  a[j] = a[j - 1];              }              a[j] = temp;          }      }                 List
      
       
         > threeSum(int[] num) {              // IMPORTANT: Please reset any member data you declared, as              // the same Solution instance will be reused for each test case.                             List
        
         
          > res=new ArrayList
          
           
            >(); if (num.length < 3) //小于3个数 return res; //对原数组非递减（递增）排序 InsertSort(num,num.length); for (int i = 0; i < num.length; ++i) { //去重 if (i != 0 && num[i] == num[i-1]) continue; int p = i + 1, q = num.length - 1; int sum = 0; //收缩法寻找第2，第3个数 while (p < q) { sum = num[i] + num[p] + num[q]; if (sum == 0) { List
            
              newRes=new ArrayList
             
              (); newRes.add(num[i]); newRes.add(num[p]); newRes.add(num[q]); //int[] newr=newRes.toArray(int[newRes.size()]); //InsertSort(newRes,newRes.size()) res.add(newRes); //寻找其他可能的2个数，顺带去重 while (++p < q && num[p-1] == num[p]) { //do nothing } while (--q > p && num[q+1] == num[q]) { //do noghing } } else if (sum < 0) //和太小，p向后移动 { ++p; } else //和过大，q向前移动 { --q; } } } return res; } }