Reference: LeetCode
Difficulty: Medium

My Post: Similar to 3Sum, Use Two Pointers [Java] Easy-Understand

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
9
10
11
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]
]

Input: [0, 0, 0, 0], and target = 0.
Output: [[0, 0, 0, 0]]

Analysis

3Sum + 4Sum

Use two pointers in 3Sum.

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
31
32
33
34
35
36
public List<List<Integer>> fourSum(int[] nums, int target) {
int n = nums.length;
// sorting
Arrays.sort(nums);
// fourSum
List<List<Integer>> result = new ArrayList<>();
for (int i = 0; i < n; ++i) {
if (i > 0 && nums[i - 1] == nums[i]) continue;
threeSum(nums, i + 1, n - 1, target - nums[i], result);
}
return result;
}

private void threeSum(int[] nums, int lo, int hi, int target, List<List<Integer>> result) {
int n = nums.length;
int subLen = hi - lo + 1;
for (int i = lo; i <= hi; ++i) {
if (i > lo && nums[i] == nums[i - 1]) continue; // skip same result
// two pointers
int j = i + 1, k = hi;
int t = target - nums[i];
while (j < k) { // each element is only used once
if (nums[j] + nums[k] < t) {
++j;
} else if (nums[j] + nums[k] > t) {
--k;
} else { // equal
result.add(Arrays.asList(nums[lo - 1], nums[i], nums[j], nums[k]));
++j;
--k;
while (j < k && nums[j] == nums[j - 1]) j++; // skip same result
while (j < k && nums[k] == nums[k + 1]) k--; // skip same result
}
}
}
}

Time: $O(N^3)$
Space: $O(1)$


Comment