题目：

?

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)

  
  

  题意：

  给定一个包含n个整数的数组S,在数组S中是否存在元素a,b,c和d,使得 a + b + c + d = target.找出数组S中所有这样的组合。

  注意：

  1.这四个元素必须是升序排列(ie, a ≤ b ≤ c ≤ d)

  2.最终结果中不嫩包含重复的解。

  ?

      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)

  
  

  ?

  算法分析：

  * 利用了题目《3Sum》的代码 https://leetcode.com/problems/3sum/
  * 首先升序排列数组，然后从第一个元素开始依次遍历《3Sum》算法，目标值为（target-nums[i]）,遍历的数组为该元素后面的数组
  * 这样既满足最终的arraylist中元素升序排列，也不会出现重复，因为每次以其为开始，进行遍历的元素都是数组中的最小的元素

  AC代码：

  ?

  public class Solution 
  {
      private static ArrayList
      
       > ret = new ArrayList
       
        >(); public ArrayList
        
         > fourSum(int[] nums, int target) { int newtarget=0; ArrayList
         
          > finalres = new ArrayList
          
           >(); Arrays.sort(nums); for (int i = 0; i < nums.length; i++) { ArrayList
           
            > temlist= new ArrayList
            
             >(); if (i > 0 && nums[i] == nums[i-1]) continue;//避免结果重复，其后面和它相等的直接被跳过。 newtarget=target-nums[i]; int inputnums[]=new int[nums.length -i-1]; for(int ii=0;ii
             
              > threeSum(int[] num,int newtarget,int firstnum) { if (num == null || num.length < 3) return ret; Arrays.sort(num); int len = num.length; for (int i = 0; i < len-2; i++) { if (i > 0 && num[i] == num[i-1]) continue;//避免结果重复，其后面和它相等的直接被跳过。 find(num, i+1, len-1, num[i],newtarget, firstnum); //寻找两个数与num[i]的和为0 } return ret; } public static void find(int[] num, int begin, int end, int target,int newtarget,int firstnum) { int l = begin, r = end; while (l < r) { if (num[l] + num[r] + target == newtarget) { ArrayList
              
                ans = new ArrayList
               
                (); ans.add(firstnum);//与原始的《3Sum》算法不同的地方为:记得把每次的启示遍历元素加入进去，就是4个数中的最小的那一个 ans.add(target); ans.add(num[l]); ans.add(num[r]); ret.add(ans); //放入结果集中 while (l < r && num[l] == num[l+1]) l++;//避免结果重复，其后面和它相等的直接被跳过。 while (l < r && num[r] == num[r-1]) r--;////避免结果重复，其后面和它相等的直接被跳过。 l++; r--; } else if (num[l] + num[r] + target < newtarget) l++; else r--; } } }
               
              
             
            
           
          
         
        
       
      

  
  
  

  ?