[LeetCode] 18. 4Sum

Posted on | In

Problem

Given an array nums of $n$ integers and an integer target, are there elements $a$, $b$, $c$, and $d$ in nums 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.

Example:

1
2
3
4
5
6
7
8
Given array nums = [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]
]

Explanation

  1. Similar to 15. 3Sum. First, we need to sort the input array. Then in the first for loop, we fix the first number. In the second for loop, we fix the second number. We also add the condition that if either these two fix numbers is the same as its previous fix numbers, we continue the for loop, so that we don’t have duplicated.

  2. After we fix the first and second number, we can use two pointers technique. We have left and right that point to the beginning and end side. We sum these four numbers and compare it with the target.

    1. If they are equal, we will add these four numbers to the result list, and check if nums[left] == nums[left+1], we then left +=1; if nums[right] == nums[right-1], we then right -= 1; so that we avoid duplicated; then we left += 1; right -= 1 to check other nums[left] and nums[right] that plus the two fix numbers if they are equal to target.

    2. If the sum is less than target, we will increase left.

    3. If the sum is greater than target, we will decrease right.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        Arrays.sort(nums);
        for (int i = 0; i < nums.length-3; i++) {
            if (i > 0 && nums[i] == nums[i-1]) continue;
            for (int j = i+1; j < nums.length-2; j++) {
                if (j > i+1 && nums[j] == nums[j-1]) continue;
                int left = j+1, right = nums.length-1;
                while (left < right) {
                    int sum = nums[i] + nums[j] + nums[left] + nums[right];
                    if (sum == target) {
                        List<Integer> sub = new ArrayList<>(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
                        res.add(sub);
                        while (left < right && nums[left] == nums[left+1]) left +=1;
                        while (left < right && nums[right] == nums[right-1]) right -= 1;
                        left += 1;
                        right -= 1;
                    } else if (sum < target) {
                        left += 1;
                    } else {
                        right -= 1;
                    }
                }
            }
        }

        return res;
    }
}