18. 4Sum (Medium)

Given an arraySofnintegers, are there elementsa,b,c, anddinSsuch thata+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]
]

Solution 1: sort O(n^3); O(1)

    public List<List<Integer>> fourSum(int[] num, int target) {
        List<List<Integer>> rst = new ArrayList<>();
        Arrays.sort(num);

        for (int i = 0; i < num.length - 3; i++) {
            if (i != 0 && num[i] == num[i - 1]) {
                continue;
            }

            for (int j = i + 1; j < num.length - 2; j++) {
                if (j != i + 1 && num[j] == num[j - 1])
                    continue;

                int left = j + 1;
                int right = num.length - 1;
                while (left < right) {
                    int sum = num[i] + num[j] + num[left] + num[right];
                    if (sum < target) {
                        left++;
                    } else if (sum > target) {
                        right--;
                    } else {
                        ArrayList<Integer> tmp = new ArrayList<>();
                        tmp.add(num[i]);
                        tmp.add(num[j]);
                        tmp.add(num[left]);
                        tmp.add(num[right]);
                        rst.add(tmp);
                        left++;
                        right--;
                        while (left < right && num[left] == num[left - 1]) {
                            left++;
                        }
                        while (left < right && num[right] == num[right + 1]) {
                            right--;
                        }
                    }
                }
            }
        }

        return rst;
    }

Solution 2: O(n^2); O(n^2)待定

    public List<List<Integer>> fourSum(int[] num, int target) {
        Arrays.sort(num);

        // for holding visited pair sums. All pairs with the same pair sum are grouped together
        Map<Integer, List<int[]>> twoSumMap = new HashMap<>(); 
        Set<List<Integer>> res = new HashSet<>(); // for holding the results

        for (int i = 0; i < num.length; i++) {
// get rid of repeated pair sums
            if (i > 1 && num[i] == num[i - 2]) continue;

            for (int j = i + 1; j < num.length; j++) {
// get rid of repeated pair sums
                if (j > i + 2 && num[j] == num[j - 2]) continue;

// for each pair sum, check if the pair sum that is needed to get the target has been visited.
                if (twoSumMap.containsKey(target - (num[i] + num[j]))) {
// if so, get all the pairs that contribute to this visited pair sum.
                    List<int[]> ls = twoSumMap.get(target - (num[i] + num[j]));

                    for (int[] pair : ls) {
// we have two pairs: one is indicated as (pair[0], pair[1]), the other is (i, j).
// we first need to check if they are overlapping with each other.
                        int m1 = Math.min(pair[0], i); // m1 will always be the smallest index
                        int m2 = Math.min(pair[1], j); // m2 will be one of the middle two indices
                        int m3 = Math.max(pair[0], i); // m3 will be one of the middle two indices
                        int m4 = Math.max(pair[1], j); // m4 will always be the largest index
                        if (m1 == m3 || m1 == m4 || m2 == m3 || m2 == m4)
                            continue; // two pairs are overlapping, so just ignore this case
                        // else record the result
                        res.add(Arrays.asList(num[m1], num[Math.min(m2, m3)], num[Math.max(m2, m3)], num[m4])); 
                    }
                }

// mark that we have visited current pair and add it to the corrsponding pair sum group.
// here we've encoded the pair indices i and j into an integer array of length 2.
                twoSumMap.computeIfAbsent(num[i] + num[j], key -> new ArrayList<>()).add(new int[]{i, j});
            }
        }

        return new ArrayList<List<Integer>>(res);
    }