18. 四数之和

一、题目

给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。

注意：

答案中不可以包含重复的四元组。

示例：

给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。

满足要求的四元组集合为：
[
[-1, 0, 0, 1],
[-2, -1, 1, 2],
[-2, 0, 0, 2]
]

二、解答

2.1方法一:排序+双指针法

public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if (nums == null || nums.length < 4){
            return result;
        }

        Arrays.sort(nums);

        for (int i = 0; i < nums.length - 3 ; i++){
            //去重
            if ( i > 0 && nums[i] == nums[i-1]){
                continue;
            }

            for (int j = i+1; j < nums.length - 2; j++){
                //去重
                if (j > i + 1 && nums[j] == nums[j-1]){
                    continue;
                }
                int l = j + 1;
                int r = nums.length - 1;

                while (l < r){
                    int sum = nums[i] + nums[j] + nums[l] + nums[r];
                    if (sum == target){
                        List<Integer> temp = new ArrayList<Integer>();
                        temp.add(nums[i]);
                        temp.add(nums[j]);
                        temp.add(nums[l] );
                        temp.add(nums[r]);
                        result.add(temp);

                        //去重
                        while (l < nums.length - 2 && nums[l] == nums[l+1]) l++;
                        while (r > 0 && nums[r] == nums[r-1]) r--;

                        l++;
                        r--;
                    }else if(sum > target){
                        r--;
                    }else {
                        l++;
                    }
                }
            }
        }

        return result;
    }

2.2方法二:排序+递归法

//K数之和的通用模板
public static ArrayList<List<Integer>> kSum(int nums[],int target,int k, int start){
        ArrayList<List<Integer>> res = new ArrayList<List<Integer>>();
        if(start>=nums.length)
            return res;
        if(k==2){
            int l = start, r = nums.length-1;
            while(l<r){
                if(nums[l]+nums[r]==target){
                    List<Integer> list = new ArrayList<Integer>();
                    list.add(nums[l]);
                    list.add(nums[r]);
                    res.add(list);
                    while(l<r&&nums[l]==nums[l+1])
                        l++;
                    while(l<r&&nums[r]==nums[r-1])
                        r--;
                    l++;
                    r--;
                }else if(nums[l]+nums[r]<target)
                    l++;
                else
                    r--;
            }
            return res;
        }
        if(k>2){
            for(int i=start;i<nums.length-k+1;i++){
                ArrayList<List<Integer>> temp = kSum(nums, target - nums[i], k - 1, i + 1);
                if(temp!=null) {
                    for (List<Integer> l : temp) {
                        l.add(0, nums[i]);
                    }
                    res.addAll(temp);
                }
                while(i<nums.length-1&&nums[i]==nums[i+1]){
                    i++;
                }
            }
            return res;
        }
        return res;
    }

    public List<List<Integer>> fourSum1(int[] nums, int target) {
        if(nums == null || nums.length < 4){
            return new ArrayList<List<Integer>>();
        }
        Arrays.sort(nums);
        return kSum(nums,target,4, 0);
    }