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.

Notice

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.

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)

Notes:

1. Fixed two pointers and then user two pointers
2. Ignore duplicate ones
3. Time: O(n^3)

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

        Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<>();
        for (int i = 0; i < nums.length-3; ++i) {
            if (i == 0 || i > 0 && nums[i] != nums[i-1]) {
                for (int j = i+1; j < nums.length-2; ++j) {
                    if (j == i+1 || j > i+1 && nums[j] != nums[j-1]) {
                        int p = j+1;
                        int q = nums.length-1;

                        while(p < q) {
                            int sum = nums[i] + nums[j] + nums[p] + nums[q];
                            if (sum == target) {
                                result.add(Arrays.asList(nums[i], nums[j], nums[p], nums[q]));

                                while(p < q && nums[p] == nums[p+1]) {
                                    p++;
                                }

                                while(p < q && nums[q] == nums[q-1]) {
                                    q--;
                                }

                                p++;
                                q--;
                            } else if (sum < target) {
                                p++;
                            } else {
                                q--;
                            }
                        }
                    }
                }
            }
        }
        return result;
    }