1. Question

给一个整型数组，找所有唯一的和为0的三个数的数对。相似的题有

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)

2. Solution

需要考虑的特殊情况：

• 数组元素个数<3
• 重复数对

2.1 O(n3)

遍历所有的三个数组成的数对，找到符合要求的。

分析：遍历过程中有很多数对是可以忽略考虑的，例如考察a、b时，如果目前发现a+b+c>0，则所有比c大的数其实都不必考虑。同理a+b+c<0时，所有比c小的数都不用再考虑。

2.2 O(n2)

2.2.1 利用2SUM（双指针）

首先对数组按升序排序，依次假设前n-2个数是符合要求的数对中的一员，对比该数大的数，采用2SUM方法找符合要求的剩余两数。

1 public class Solution { 2     //O(n2) 3     public List< List< Integer > > threeSum( int[] num ){ 4         int len = num.length; 5         ArrayList< List< Integer> > res = new ArrayList
         
          
           >(); 6         if( len<3 ) 7             return res; 8         Arrays.sort( num ); 9         10         if( num[0]>0 || num[len-1]<0 )11             return res;12         13         HashSet< List
           
             > test = new HashSet< List< Integer> >();14         for( int i=0; i
            
              aTriple = new ArrayList< Integer >();20                     aTriple.add( num[i]);21                     aTriple.add( num[j]);22                     aTriple.add( num[k]);23                     if( test.add( aTriple ))24                         res.add( aTriple );25                     j++;26                     k--;27                 }28                 else if( now<0 )29                     j++;30                 else31                     k--;32             }33         }34         35         return res;        36     }37 }
            
           
          
         

 

2.2.2 利用2SUM（map）

map可以不用排序，同时实现找的时间为常数时间。是最符合人思维的方式。

public class Solution {    private void addToRes( List
         
          
           > res, int i, int j, int k ){        ArrayList< Integer > aTriple = new ArrayList< Integer >();        aTriple.add( i );        aTriple.add( j );        aTriple.add( k );        res.add(aTriple);    }        //o(n2)    public List< List< Integer> > threeSum( int[] num ){        ArrayList< List< Integer> > res = new ArrayList
           
            < Integer> >();        if( num.length < 3 )            return res;        Arrays.sort( num );        int len = num.length;        if( num[len-1] < 0 || num[0] > 0 )            return res;        if( (num[0]==0 && num[2]==0 ) || ( num[len-1]==0 && num[len-3] ==0 ) ){            addToRes( res, 0, 0, 0 );            return res;        }        HashMap
            
              sortNum = new HashMap< Integer, Integer >();        int count = 0;        int i=0;        while( i < len ){            if( sortNum.containsValue( num[i]) ){                if( i
             
              =0 ){                        if( num[i] < 0 )                            addToRes( res, num[i], num[i], -2 * num[i] );                        else                            addToRes( res, -2*num[i], num[i], num[i] );                    }                                    }                while( ++i