https://oj.leetcode.com/problems/3sum/

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)

解题思路：

三个加数，首先想到排序，快排花费时间O(n*logn)。然后想到从头和尾各确定一个数字，在他们中间用二分法找第三个加数。时间复杂度O(n*logn + n^2 * logn)，超时。

于是想到，由之前的two sum那道题，已知一个加数，求另一个加数，很容易想到用hashmap，在O(n)的时间内求解。这样就可以省去找第三个数字的对数时间。将时间复杂度减少到O(n^2)。

public class Solution {    public List
     
      
       > threeSum(int[] num) {        Arrays.sort(num);                HashMap
       
         hashMap = new HashMap
        
         ();                for(int i = 0; i < num.length; i++){            hashMap.put(num[i], i);        }                Set
         
           leftSet = new HashSet
          
           (); Set
           
             rightSet = new HashSet
            
             (); List
             
              
               > resultList = new ArrayList
               
                
                 >(); for(int i = 0; i < num.length / 2; i++){ for(int j = num.length - 1; j > i; j--){ int left = 0 - num[i] - num[j]; //用二分法查找第三个元素，超时 // int start = i + 1; // int end = j - 1; // while(start <= end){ // int mid = (start + end) / 2; // if(num[mid] > left){ // end = mid - 1; // } // if(num[mid] < left){ // start = mid + 1; // } // if(num[mid] == left){ // List
                 
                   list = new ArrayList
                  
                   (); // list.add(num[i]); // list.add(num[mid]); // list.add(num[j]); // resultList.add(list); // break; // } // } //用hashmap查找第三个元素 if(hashMap.containsKey(left) && hashMap.get(left) != i && hashMap.get(left) != j && !leftSet.contains(num[i]) && !rightSet.contains(num[j])){ List
                   
                     list = new ArrayList
                    
                     (); list.add(num[i]); list.add(left); list.add(num[j]); resultList.add(list); leftSet.add(num[i]); rightSet.add(num[j]); // break; } } } return resultList; }}
                    
                   
                  
                 
                
               
              
             
            
           
          
         
        
       
      
     

但是这个解法会遇到一个很复杂的问题，HashMap无法确定重复元素的位置。于是重新找思路。

下面是一个可行的解法。和上面的解法思路类似，但是不同。也是先排序，从头至尾遍历数组，只确定一个数num[i]，然后找剩下的两个数。那么这两个数一定在[i + 1, num.length - 1]。如果这三个数字和==0，那么就是解答了，如果>0，证明end--，如果<0，那么start++。这很容易理解。

需要注意的就是去除重复答案的处理过程。第一个遍历加数，如果当前处理数字和前一个相等，也就是num[i] == num[i - 1]，就可以跳过了。因为num[i]已经在[i + 1, num.length - 1]的区间内求解结束了。num[i + 1]和num[i]相等，在后面更小的一个区间内，即使有解，也一定是重复的。

注意这里一定是判断num[i] == num[i - 1]，而不是num[i] == num[i + 1]，因为要和前面已经求过解的元素比较，而不是后面为求解的元素。同理对于start和end的处理。

public class Solution {    public List
     
      
       > threeSum(int[] num) {        Arrays.sort(num);                List
       
        
         > resultList = new ArrayList
         
          
           >(); for(int i = 0; i < num.length - 2; i++){ //必须与前一个数字相比，和已经处理过的数字比，如果重复，就跳过 if(i > 0 && num[i] == num[i - 1]){ continue; } int start = i + 1; int end = num.length - 1; while(start < end){ if(start > i + 1 && num[start] == num[start - 1]){ start++; continue; } if(end < num.length - 1 && num[end] == num[end + 1]){ end--; continue; } if(num[i] + num[start] + num[end] == 0){ List list = new ArrayList(); list.add(num[i]); list.add(num[start]); list.add(num[end]); resultList.add(list); start++; end--; }else if(num[i] + num[start] + num[end] > 0){ end--; }else if(num[i] + num[start] + num[end] < 0){ start++; } } } return resultList; }}
          
         
        
       
      
     

 由上面的解法我们可以知道，对于一个已经排序的数组，找两个sum确定的数字，是一个在O(n)的时间内求解的。