题目要求

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: 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]]

输入一个整数数组，从中找到所有的三个整数组成一个数组，这三个整数的和为0。要求不包括重复的结果

思路一：无hashset or hashmap

这里使用了三个指针。

public List
    
     
      > threeSum2(int[] nums) {           List
      
       
        > result = new ArrayList
        
         
          >(); int length = nums.length; if(length<3){ return result; } Arrays.sort(nums); int i = 0; while(i
          
           0) break; int j = i+1; int k = nums.length - 1; while(j
           
            =0){ //消去右侧重复的数字 while(nums[k--] == nums[k] && j < k); } //消去和当前左指针相同的数字 while(nums[i] == nums[++i] && i < nums.length - 2); } } return result; }
           
          
         
        
       
      
     
    

思路二：有hashmap/hashset

利用hashmap/hashset是为了避开重复的值，但是效率值明显不如上一种方法高

public List
    
     
      > threeSum(int[] num) {    Arrays.sort(num);    List
      
       
        > list = new ArrayList
        
         
          >(); HashSet
          
           
            > set = new HashSet
            
             
              >(); for(int i=0;i
              
                l= new ArrayList
               
                (); l.add(num[i]); l.add(num[j]); l.add(num[k]); if(set.add(l)) list.add(l); j++; k--; } else if(num[i]+num[j]+num[k]<0) j++; else k--; } } return list;}