原题链接在这里：

题目：

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

题解：

这道题其实是的扩展，使用的方法基本相同，只是多加了一层loop.

但要注意一点：For inner j loop, if statement, 判断overflow 时要写成 j>i+1, 而不是j>0, 与 j 的 初始条件有关。若是写成j>0的话，含有四个相同数的输入就会被跳过. e.g. 0,0,0,0 target = 0.

Time Complexity: O(n^3), 两层for, 每一层用时n, 内层for里面的while 用了O(n) time, 一共用了O(n^3).

Space: O(1), regardless res.

AC Java:

1 public class Solution { 2     public List
     
      
       > fourSum(int[] nums, int target) { 3         List
       
        
         > res = new ArrayList
         
          
           >(); 4 if(nums == null || nums.length < 4){ 5 return res; 6 } 7 8 Arrays.sort(nums); 9 for(int i = 0; i
           
            0 && nums[i] == nums[i-1]){11 continue;12 }13 14 for(int j = i+1; j
            
             i+1 && nums[j] == nums[j-1]){16 continue;17 }18 19 int l = j+1;20 int r = nums.length-1;21 while(l
             
               target){26 r--;27 }else{28 List
              
                item = new ArrayList
               
                ();29 item.add(nums[i]);30 item.add(nums[j]);31 item.add(nums[l]);32 item.add(nums[r]);33 res.add(item);34 l++;35 r--;36 while(l
               
              
             
            
           
          
         
        
       
      
     

类似.