4Sum 解答

Question

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:

• Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ≤ b ≤ c ≤ d)
• 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)

Solution

我们可以follow 3Sum的思路完成4Sum。

这里给出average time小于O(n³)的方法。

我们可以把4Sum拆解为2Sum的问题。首先，构造map，key为pair sum，value为list of pairs。然后，照着2Sum的方法，得出结果。

public class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        Map<Integer, List<List<Integer>>> map = new HashMap<Integer, List<List<Integer>>>();
        Set<List<Integer>> result = new HashSet<List<Integer>>();
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                int sum = nums[i] + nums[j];
                if (map.containsKey(target - sum)) {
                    List<List<Integer>> pairs = map.get(target - sum);
                    for (List<Integer> pair : pairs) {
                        // m1 < m2
                        int m1 = pair.get(0);
                        int m2 = pair.get(1);
                        // m3 < m4
                        int m3 = i;
                        int m4 = j;
                        if (m1 == m3 || m1 == m4 || m2 == m3 || m2 == m4) {
                            continue;
                        } else {
                            if (m2 < m3) {
                                result.add(Arrays.asList(nums[m1], nums[m2], nums[m3], nums[m4]));
                            } else if (m2 > m4) {
                                result.add(Arrays.asList(nums[m1], nums[m3], nums[m4], nums[m2]));
                            } else {
                                result.add(Arrays.asList(nums[m1], nums[m3], nums[m2], nums[m4]));
                            }
                        }
                    }
                }
                // Add current pair into map
                List<Integer> list = new ArrayList<Integer>();
                list.add(i);
                list.add(j);
                if (map.containsKey(sum)) {
                    map.get(sum).add(list);
                } else {
                    List<List<Integer>> tmp2 = new ArrayList<Lis<Integer>>();
                    tmp2.add(list);
                    map.put(sum, tmp2);
                }
                
            }
        }
        return new ArrayList<List<Integer>>(result);
    }
}