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)

Best 做法：不用Extra Space, Time Complexity still O(N^2)

1 public class Solution { 2     public List
     
      
       > threeSum(int[] num) { 3         List
       
        
         > res = new ArrayList
         
          
           >(); 4 if (num == null || num.length < 3) { 5 return res; 6 } 7 Arrays.sort(num); 8 for (int i=num.length-1; i>=2; i--) { 9 if (i
           
            > res, int lastInTriplet) {16 while (l < r) {17 if (num[l] + num[r] == target) {18 List
            
              set = new ArrayList
             
              ();19 set.add(num[l]);20 set.add(num[r]);21 set.add(lastInTriplet);22 res.add(new ArrayList
              
               (set));23 l++;24 r--;25 while (l
               
                 target) {33 r--;34 }35 else {36 l++;37 }38 }39 }40 }
               
              
             
            
           
          
         
        
       
      
     

 

第一遍做法：用了Extra Space

总的时间复杂度为O(NlongN + N^2) = O(N^2)

1 public class Solution { 2     public ArrayList
     
      
       > threeSum(int[] num) { 3         ArrayList
       
        
         > res = new ArrayList
         
          
           >(); 4 if (num == null || num.length < 3) { 5 return res; 6 } 7 Arrays.sort(num); 8 for (int i=num.length-1; i>=2; i--) { 9 if (i
           
            > sumOfTwo = twoSum(num, 0, i-1, -num[i]);11 for (int k=0; k
            
              temp = sumOfTwo.get(k);13 temp.add(num[i]);14 }15 res.addAll(sumOfTwo);16 }17 return res;18 }19 20 public ArrayList
             
              
               > twoSum(int[] num, int l, int r, int target) {21 ArrayList
               
                
                 > sets = new ArrayList
                 
                  
                   >();22 while (l < r) {23 if (num[l] + num[r] == target) {24 ArrayList
                   
                     set = new ArrayList
                    
                     ();25 set.add(num[l]);26 set.add(num[r]);27 sets.add(new ArrayList
                     
                      (set));28 l++;29 r--;30 while (l
                      
                        target) {38 r--;39 }40 else {41 l++;42 }43 }44 return sets;45 }46 }
                      
                     
                    
                   
                  
                 
                
               
              
             
            
           
          
         
        
       
      
     

 注意22、30、33行都只能用<而不是 <=， <=会导致l 与 r有可能重合，相当于取同一个元素两次，而实际上不存在这种情况。

一个例子就是

Input:	[1,2,-2,-1]
Output:	[[-1,-1,2]]
Expected:	[]

在[-2, -1, 1]当中寻找和为-2，答案应该是不存在，但是如果我们设置l <= r，则当l r都为-1则会得到一组答案，而实际上是不满足条件的