4 Sum
Given an array numstarget[nums[a], nums[b], nums[c], nums[d]]target
Example 1
Output: [[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]
Example 2
Output: [[2, 2, 2, 2]]
How to Think About It
Step 1: Build on 3Sum
Step 2: The inner search
After fixing indices ijlojhi
- sum too small: move
right;lo - sum too big: move
left;hi - equal: record the quadruplet and move both.
Step 3: Skip duplicates at every level
Sorting puts equal values together. Skip inums[i]jlo
Step 4: Watch for overflow
Values go up to 109, so four of them can exceed an intlong
Walkthrough
nums[-2, -1, 0, 0, 1, 2]
| Fixed values | Need from the rest | Pairs found by lo and hi | Quadruplets |
|---|---|---|---|
| -2, -1 | 3 | 1 + 2 | [-2, -1, 1, 2] |
| -2, 0 | 2 | 0 + 2 | [-2, 0, 0, 2] |
| -2, 0 (second 0) | skipped: same as the previous j | ||
| -1, 0 | 1 | 0 + 1 | [-1, 0, 0, 1] |
Java Solution
fourSumijlohi
- Loop bounds:
andi < n - 3 leave room for the values still to be chosen, so a three-value array such asj < n - 2 returns[1, 2, 3] without any search.[] - The sum is a long: four values near 109 add up to about 4 × 109, beyond
. The cast onint makes the whole addition run innums[i] .long - Repeats at both levels:
skips only repeats inside the currentj > i + 1 , soi with target 8 still finds[2, 2, 2, 2, 2] , exactly once.[2, 2, 2, 2]
A common mistake is an intintlong[]
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class FourSum {
public static List<List<Integer>> fourSum(int[] nums, int target) {
Arrays.sort(nums);
List<List<Integer>> result = new ArrayList<>();
int n = nums.length;
for (int i = 0; i < n - 3; i++) {
if (i > 0 && nums[i] == nums[i - 1]) {
continue; // same first value: same quadruplets
}
for (int j = i + 1; j < n - 2; j++) {
if (j > i + 1 && nums[j] == nums[j - 1]) {
continue; // same second value
}
int lo = j + 1;
int hi = n - 1;
while (lo < hi) {
long sum = (long) nums[i] + nums[j] + nums[lo] + nums[hi]; // can overflow int
if (sum < target) {
lo++;
} else if (sum > target) {
hi--;
} else {
result.add(List.of(nums[i], nums[j], nums[lo], nums[hi]));
lo++;
hi--;
while (lo < hi && nums[lo] == nums[lo - 1]) {
lo++; // skip repeats of the third value
}
}
}
}
}
return result;
}
public static void main(String[] args) {
System.out.println(fourSum(new int[] {1, 0, -1, 0, -2, 2}, 0));
// [[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]
System.out.println(fourSum(new int[] {2, 2, 2, 2, 2}, 8)); // [[2, 2, 2, 2]]
}
}
The original implementation,
Complexity
- Time: O(n³). The sort is O(n log n); the two nested loops choose about n²/2 pairs (
,i ), and for each pair the two-pointer pass over the rest of the array takes O(n) steps.j - Space: O(1) besides the output and the sort. Only the indexes and the
sum are extra; the quadruplets inlong are the answer, and the in-place sort uses only a small recursion stack.result
For counting zero-sum tuples across four separate arrays, a hash map does better: see