Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note:

• Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ≤ b ≤ c ≤ d)
• The solution set must not contain duplicate quadruplets.

 

For example, given array S = {1 0 -1 0 -2 2}, and target = 0.    A solution set is:    (-1,  0, 0, 1)    (-2, -1, 1, 2)    (-2,  0, 0, 2) 解题思路： 　　4个指针， 前两个指针双循环遍历数组，第三个指针放在第二个指针之后，第四个指针放在末尾，求和和target比较，如果 sum > target 最后一个指针--， 如果sum < target 第三个指针++; 相等先判断是否是重复的（hashset）,如果不是添加到result中去；

1 public class Solution { 2     public ArrayList
      
       
        > fourSum(int[] num, int target) { 3         Arrays.sort(num); 4         ArrayList
        
         
          > result = new ArrayList
          
           
            >(); 5 HashSet
            
             
              > set = new HashSet
              
               
                >(); 6 int len = num.length; 7 for(int i = 0; i< len; i++){ 8 for(int j = i+1; j < len; j++){ 9 int k = j+1;10 int l = len-1;11 12 while(k < l){13 int sum = num[i]+num[j]+num[k]+num[l];14 15 if(sum < target){16 k++;17 }else if(sum > target){18 l--;19 }else {20 ArrayList
                
                  output = new ArrayList
                 
                  ();21 output.add(num[i]);22 output.add(num[j]);23 output.add(num[k]);24 output.add(num[l]);25 if(! set.contains(output)){26 set.add(output);27 result.add(output);28 }29 k++;30 l--;31 } 32 } 33 }34 }35 36 return result;37 38 }39 }