18. 4Sum

Given S an array 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]
]

思路： 在3Sum上再套一层

public class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();

        Arrays.sort(nums);

        for (int i=0;i<nums.length-3;i++){
            int target3 = target-nums[i];
            if (i==0||(i>0&&nums[i]!=nums[i-1])){
                for (int j=i+1;j<nums.length-2;j++){
                    int target2 = target3 - nums[j];
                    if (j==i+1||(j>i+1&&nums[j]!=nums[j-1])){
                        int left = j+1;
                        int right = nums.length-1;
                        while (left<right){
                            int sum = nums[left]+nums[right];
                            if (sum==target2){
                                List<Integer> tmp = new ArrayList<Integer>();
                                tmp.add(nums[i]);
                                tmp.add(nums[j]);
                                tmp.add(nums[left]);
                                tmp.add(nums[right]);
                                result.add(tmp);

                                while(left<right&&nums[left]==nums[left+1]){
                                    left++;
                                }
                                while(left<right&&nums[right]==nums[right-1]){
                                    right--;
                                }
                                left++;
                                right--;
                            }else if(sum<target2){
                                left++;
                            }else{
                                right--;
                            }
                        }
                    }
                }    
            }

        }

        return result;
    }
}