LeetCode 18: 4Sum (Sorting + Two Pointers + Dedup)
LeetCode 18Two PointersSortingToday we solve LeetCode 18 - 4Sum.
Source: https://leetcode.com/problems/4sum/
English
Problem Summary
Given an integer array nums and target target, return all unique quadruplets [a,b,c,d] such that a+b+c+d=target.
Key Insight
Sort first. Fix the first two numbers with nested loops, then solve the remaining pair by two pointers. Duplicate skipping at every level is mandatory to avoid repeated quadruplets.
Optimal Algorithm Steps
1) Sort nums.
2) Loop i from 0 to n-4, skip duplicate nums[i].
3) Loop j from i+1 to n-3, skip duplicate nums[j].
4) Set l=j+1, r=n-1, compute 4-sum.
5) If sum equals target, record result and move both pointers while skipping duplicates.
6) If sum < target move l++, else r--.
Complexity Analysis
Time: O(n^3).
Space: O(1) extra (excluding output).
Common Pitfalls
- Missing duplicate checks for i, j, l, r.
- Integer overflow when summing 4 ints (use long where needed).
- Only moving one pointer after finding a valid quadruplet.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
import java.util.*;
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
Arrays.sort(nums);
List<List<Integer>> ans = new ArrayList<>();
int n = nums.length;
for (int i = 0; i < n - 3; i++) {
if (i > 0 && nums[i] == nums[i - 1]) continue;
for (int j = i + 1; j < n - 2; j++) {
if (j > i + 1 && nums[j] == nums[j - 1]) continue;
int l = j + 1, r = n - 1;
while (l < r) {
long sum = (long) nums[i] + nums[j] + nums[l] + nums[r];
if (sum == target) {
ans.add(Arrays.asList(nums[i], nums[j], nums[l], nums[r]));
l++; r--;
while (l < r && nums[l] == nums[l - 1]) l++;
while (l < r && nums[r] == nums[r + 1]) r--;
} else if (sum < target) l++;
else r--;
}
}
}
return ans;
}
}import "sort"
func fourSum(nums []int, target int) [][]int {
sort.Ints(nums)
n := len(nums)
ans := [][]int{}
for i := 0; i < n-3; i++ {
if i > 0 && nums[i] == nums[i-1] { continue }
for j := i + 1; j < n-2; j++ {
if j > i+1 && nums[j] == nums[j-1] { continue }
l, r := j+1, n-1
for l < r {
sum := int64(nums[i]) + int64(nums[j]) + int64(nums[l]) + int64(nums[r])
if sum == int64(target) {
ans = append(ans, []int{nums[i], nums[j], nums[l], nums[r]})
l++; r--
for l < r && nums[l] == nums[l-1] { l++ }
for l < r && nums[r] == nums[r+1] { r-- }
} else if sum < int64(target) { l++ } else { r-- }
}
}
}
return ans
}class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
sort(nums.begin(), nums.end());
vector<vector<int>> ans;
int n = nums.size();
for (int i = 0; i < n - 3; ++i) {
if (i > 0 && nums[i] == nums[i - 1]) continue;
for (int j = i + 1; j < n - 2; ++j) {
if (j > i + 1 && nums[j] == nums[j - 1]) continue;
int l = j + 1, r = n - 1;
while (l < r) {
long long sum = 1LL * nums[i] + nums[j] + nums[l] + nums[r];
if (sum == target) {
ans.push_back({nums[i], nums[j], nums[l], nums[r]});
++l; --r;
while (l < r && nums[l] == nums[l - 1]) ++l;
while (l < r && nums[r] == nums[r + 1]) --r;
} else if (sum < target) ++l;
else --r;
}
}
}
return ans;
}
};class Solution:
def fourSum(self, nums: list[int], target: int) -> list[list[int]]:
nums.sort()
n = len(nums)
ans = []
for i in range(n - 3):
if i > 0 and nums[i] == nums[i - 1]:
continue
for j in range(i + 1, n - 2):
if j > i + 1 and nums[j] == nums[j - 1]:
continue
l, r = j + 1, n - 1
while l < r:
s = nums[i] + nums[j] + nums[l] + nums[r]
if s == target:
ans.append([nums[i], nums[j], nums[l], nums[r]])
l += 1
r -= 1
while l < r and nums[l] == nums[l - 1]:
l += 1
while l < r and nums[r] == nums[r + 1]:
r -= 1
elif s < target:
l += 1
else:
r -= 1
return ansvar fourSum = function(nums, target) {
nums.sort((a, b) => a - b);
const ans = [];
const n = nums.length;
for (let i = 0; i < n - 3; i++) {
if (i > 0 && nums[i] === nums[i - 1]) continue;
for (let j = i + 1; j < n - 2; j++) {
if (j > i + 1 && nums[j] === nums[j - 1]) continue;
let l = j + 1, r = n - 1;
while (l < r) {
const sum = nums[i] + nums[j] + nums[l] + nums[r];
if (sum === target) {
ans.push([nums[i], nums[j], nums[l], nums[r]]);
l++; r--;
while (l < r && nums[l] === nums[l - 1]) l++;
while (l < r && nums[r] === nums[r + 1]) r--;
} else if (sum < target) l++;
else r--;
}
}
}
return ans;
};中文
题目概述
给定整数数组 nums 和目标值 target，找出所有不重复四元组 [a,b,c,d]，使得四数之和等于 target。
核心思路
先排序，前两层用双循环固定前两个数，后两位使用双指针线性扫描。关键是每一层都跳过重复值，保证答案去重。
最优算法步骤
1）数组升序排序。
2）遍历 i，重复值跳过。
3）遍历 j，重复值跳过。
4）设 l=j+1, r=n-1，计算四数和。
5）若命中目标，记录结果并移动双指针，同时跳过重复。
6）和太小左移 l，和太大右移 r。
复杂度分析
时间复杂度：O(n^3)。
空间复杂度：O(1) 额外空间（不计输出）。
常见陷阱
- 任何一层漏掉去重都会产生重复答案。
- 四数求和可能溢出，Java/C++ 应使用更大整数类型。
- 命中后只移动一个指针，可能死循环或漏解。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
import java.util.*;
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
Arrays.sort(nums);
List<List<Integer>> ans = new ArrayList<>();
int n = nums.length;
for (int i = 0; i < n - 3; i++) {
if (i > 0 && nums[i] == nums[i - 1]) continue;
for (int j = i + 1; j < n - 2; j++) {
if (j > i + 1 && nums[j] == nums[j - 1]) continue;
int l = j + 1, r = n - 1;
while (l < r) {
long sum = (long) nums[i] + nums[j] + nums[l] + nums[r];
if (sum == target) {
ans.add(Arrays.asList(nums[i], nums[j], nums[l], nums[r]));
l++; r--;
while (l < r && nums[l] == nums[l - 1]) l++;
while (l < r && nums[r] == nums[r + 1]) r--;
} else if (sum < target) l++;
else r--;
}
}
}
return ans;
}
}import "sort"
func fourSum(nums []int, target int) [][]int {
sort.Ints(nums)
n := len(nums)
ans := [][]int{}
for i := 0; i < n-3; i++ {
if i > 0 && nums[i] == nums[i-1] { continue }
for j := i + 1; j < n-2; j++ {
if j > i+1 && nums[j] == nums[j-1] { continue }
l, r := j+1, n-1
for l < r {
sum := int64(nums[i]) + int64(nums[j]) + int64(nums[l]) + int64(nums[r])
if sum == int64(target) {
ans = append(ans, []int{nums[i], nums[j], nums[l], nums[r]})
l++; r--
for l < r && nums[l] == nums[l-1] { l++ }
for l < r && nums[r] == nums[r+1] { r-- }
} else if sum < int64(target) { l++ } else { r-- }
}
}
}
return ans
}class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
sort(nums.begin(), nums.end());
vector<vector<int>> ans;
int n = nums.size();
for (int i = 0; i < n - 3; ++i) {
if (i > 0 && nums[i] == nums[i - 1]) continue;
for (int j = i + 1; j < n - 2; ++j) {
if (j > i + 1 && nums[j] == nums[j - 1]) continue;
int l = j + 1, r = n - 1;
while (l < r) {
long long sum = 1LL * nums[i] + nums[j] + nums[l] + nums[r];
if (sum == target) {
ans.push_back({nums[i], nums[j], nums[l], nums[r]});
++l; --r;
while (l < r && nums[l] == nums[l - 1]) ++l;
while (l < r && nums[r] == nums[r + 1]) --r;
} else if (sum < target) ++l;
else --r;
}
}
}
return ans;
}
};class Solution:
def fourSum(self, nums: list[int], target: int) -> list[list[int]]:
nums.sort()
n = len(nums)
ans = []
for i in range(n - 3):
if i > 0 and nums[i] == nums[i - 1]:
continue
for j in range(i + 1, n - 2):
if j > i + 1 and nums[j] == nums[j - 1]:
continue
l, r = j + 1, n - 1
while l < r:
s = nums[i] + nums[j] + nums[l] + nums[r]
if s == target:
ans.append([nums[i], nums[j], nums[l], nums[r]])
l += 1
r -= 1
while l < r and nums[l] == nums[l - 1]:
l += 1
while l < r and nums[r] == nums[r + 1]:
r -= 1
elif s < target:
l += 1
else:
r -= 1
return ansvar fourSum = function(nums, target) {
nums.sort((a, b) => a - b);
const ans = [];
const n = nums.length;
for (let i = 0; i < n - 3; i++) {
if (i > 0 && nums[i] === nums[i - 1]) continue;
for (let j = i + 1; j < n - 2; j++) {
if (j > i + 1 && nums[j] === nums[j - 1]) continue;
let l = j + 1, r = n - 1;
while (l < r) {
const sum = nums[i] + nums[j] + nums[l] + nums[r];
if (sum === target) {
ans.push([nums[i], nums[j], nums[l], nums[r]]);
l++; r--;
while (l < r && nums[l] === nums[l - 1]) l++;
while (l < r && nums[r] === nums[r + 1]) r--;
} else if (sum < target) l++;
else r--;
}
}
}
return ans;
};
Comments