[LeetCode]--18. 4Sum

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

借鉴三个数的方法，固定两个数，再用两个指针去搜寻。

public class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        int len = nums.length;
        Arrays.sort(nums);
        if (len < 4)
            return res;
        for (int i = 0; i < len - 1; i++) {
            if (i > 0 && nums[i] == nums[i - 1])
                continue;
            for (int j = i + 1; j < len; j++) {
                if (j > i + 1 && nums[j] == nums[j - 1])
                    continue;
                int begin = j + 1, end = len - 1;
                while (begin < end) {
                    int sum = nums[i] + nums[j] + nums[begin] + nums[end];
                    if (sum == target) {
                        List<Integer> list = new ArrayList<Integer>();
                        list.add(nums[i]);
                        list.add(nums[j]);
                        list.add(nums[begin]);
                        list.add(nums[end]);
                        res.add(list);
                        begin++;
                        end--;
                        while (begin < end && nums[begin] == nums[begin - 1])
                            begin++;
                        while (begin < end && nums[end] == nums[end + 1])
                            end--;
                    } else if (sum > target)
                        end--;
                    else
                        begin++;
                }
            }
        }
        return res;
    }
}

另外一种就是固定一个数，调用取三个数的算法。

public List<List<Integer>> fourSum1(int[] nums, int target) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            int check = target - nums[i];
            if (i > 0 && nums[i - 1] == nums[i])
                continue;
            List<List<Integer>> getThreeSums = threeSum(nums, i + 1,
                    nums.length - 1, check);
            for (List<Integer> subList : getThreeSums) {
                subList.add(nums[i]);
                result.add(subList);
            }
        }
        return result;
    }

    public List<List<Integer>> threeSum(int[] nums, int begin, int finish,
            int target) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        for (int i = begin; i <= finish; i++) {
            if (i > begin && nums[i - 1] == nums[i])
                continue;
            int start = i + 1;
            int end = finish;
            int check = target - nums[i];
            while (start < end) {
                int twoSum = nums[start] + nums[end];
                if (twoSum > check)
                    end--;
                else if (twoSum < check)
                    start++;
                else {
                    List<Integer> subResult = new ArrayList<Integer>();
                    subResult.add(nums[i]);
                    subResult.add(nums[start++]);
                    subResult.add(nums[end--]);
                    result.add(subResult);
                    while (start < end && nums[start] == nums[start - 1])
                        start++;
                    while (start < end && nums[end] == nums[end + 1])
                        end--;
                }
            }
        }
        return result;
    }