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

 

从数组中找出四个字之和为target的。因为有多组，所以要从头遍历到尾。

 

找出四个数之和为target，做法和三个数之和一样，就是外面多套一层循环。也就是 先排序，遍历数组，然后从剩下的数组中找出三个元素与当前元素之和为target，三个元素之和又是遍历剩下的数组，再从剩剩下的数组中找出两个数，使他们与前两个遍历的元素的和为target，这两个元素从两头往中间遍历。期间要跳过重复元素。具体见代码。每次遍历时还可以多加判断条件，如当前元素和最后三个元素 的和小于target，这时就进入下轮循环了，要使左边数字增大才行。

 

class Solution {    public List
      
       
        > fourSum(int[] nums, int target) {        Arrays.sort(nums);        List
        
         
          > result=new ArrayList
          
           
            >(); for(int i=0;i
            
             target) break;//前面四个都已经大于target了，就说明没有了（有序） //当前数字和最后三个数字的和小于target，则将当前数字后移，也就是进行下一个循环 if(nums[i]+nums[nums.length-1]+nums[nums.length-2]+nums[nums.length-3]
             
              0&&nums[i]!=nums[i-1])){ for(int j=i+1;j
              
               target) break; if(nums[i]+nums[j]+nums[nums.length-1]+nums[nums.length-2]
               
                i+1&&nums[j]!=nums[j-1])){ int left=j+1,right=nums.length-1,sum=target-nums[i]-nums[j]; while(left
                
                 sum) { right--; }else{ left++; } } } } } } return result; }}