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

Array类题目。

##Approach 1 与之前的3 sum类似，多套一层循环，因此时间复杂度为O(n^3)。 首先对数组进行排序，然后每确定第一个数，问题就转化为3 sum。

public class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        if(nums == null || nums.length < 4) {
            return res;
        }
        Arrays.sort(nums);
        for(int i = 0; i < nums.length-3; i++) {
            if(i > 0 && nums[i] == nums[i-1]) continue; // skip duplication
            for(int j = i+1; j < nums.length-2; j++) {
                if(j > i+1 && nums[j] == nums[j-1]) continue; // skip duplication
                int newTar = target - nums[i] - nums[j]; // 2 sum
                int l = j+1, r = nums.length-1;
                while(l < r) {
                    if(l > j+1 && nums[l] == nums[l-1]) {
                        l++;
                        continue;
                    }
                    if(r < nums.length-1 && nums[r] == nums[r+1]) {
                        r--;
                        continue;
                    }
                    int sum = nums[l] + nums[r];
                    if(sum == newTar) {
                        res.add(Arrays.asList(nums[i], nums[j], nums[l], nums[r]));
                        l++;
                        r--;
                    } else if(sum < newTar) {
                        l++;
                    } else {
                        r--;
                    }
                }
                
            }
        }
        return res;
    }
}

##Approach 2 虽然时间复杂度需要O(n^3)，但是我们在确定一个数字时，可以加以选择，加快搜索的过程。 比如，选择第一个数first时，我们可以过滤到以下几种情形：

1. first + 3 * max < target: first太小了，继续向下搜寻；
2. 4 * first > target: first太大了，由于数组已经排过序，因此后面不会再有解，可以退出；
3. 4 * first == target: 若有四个first，则这是一个解，否则退出，后面也不会再有解。

这样过滤后的值是first的有效candidates，在这些值中再以同样方法去找3 sum。 虽然时间复杂度仍是O(n^3)，但是实际的计算次数减少了。

public class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        if(nums == null || nums.length < 4) {
            return res;
        }
        Arrays.sort(nums);
        int max = nums[nums.length-1];
        if(4*nums[0] > target || 4*max < target) {
            return res;
        }
        for(int i = 0; i < nums.length-3; i++) {
            int cur = nums[i];
            if(i > 0 && cur == nums[i-1]) continue; // skip duplication
            if(cur + 3*max < target) continue; // cur is too small
            if(4*cur > target) break; // cur is too large
            if(4*cur == target) {
                if(cur == nums[i+3]) {
                    res.add(Arrays.asList(cur,cur,cur,cur));
                }
                break;
            }
            threeSum(nums, target-cur, i+1, nums.length-1, res, cur);
        }
        return res;
    }
    
    private void threeSum(int[] nums, int target, int low, int high, List<List<Integer>> res, int first) {
        if(high - low < 2) return;
        int max = nums[high];
        if(3*nums[low] > target || 3*max < target) {
            return;
        }
        for(int i = low; i < high-1; i++) {
            int cur = nums[i];
            if(i > low && cur == nums[i-1]) continue; // skip duplication
            if(cur + 2*max < target) continue; // cur is too small
            if(3*cur > target) break; // cur is too large
            if(3*cur == target) {
                if(cur == nums[i+2]) {
                    res.add(Arrays.asList(first,cur,cur,cur));
                }
                break;
            }
            twoSum(nums, target-cur, i+1, high, res, first, cur);
        }
    }
    
    private void twoSum(int[] nums, int target, int low, int high, List<List<Integer>> res, int first, int second) {
        if(high - low < 1) return;
        if(2*nums[low] > target || 2*nums[high] < target) {
            return;
        }
        int l = low, r = high;
        while(l < r) {
            if(l > low && nums[l] == nums[l-1]) {
                l++;
                continue;
            }
            if(r < high && nums[r] == nums [r+1]) {
                r--;
                continue;
            }
            int sum = nums[l] + nums[r];
            if(sum == target) {
                res.add(Arrays.asList(first, second, nums[l], nums[r]));
                l++;
                r--;
            } else if(sum < target) {
                l++;
            } else {
                r--;
            }
        }
    }
}