18. 四数之和
题目描述
输入由 n 个整数组成的数组 nums 和整数 target。
选出四个互不相同的下标 a、b、c、d（都在 0 到 n - 1 之间）。如果这四个位置上的数加起来恰好等于 target，它们就组成一个四元组。
返回所有不重复的四元组。两个四元组的元素能一一对应时视为重复，只保留一个。返回顺序不限。
示例 1
输入：nums = [1,0,-1,0,-2,2], target = 0 输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
解释：共有三组不同的四个数，和都为 0。
示例 2
输入：nums = [2,2,2,2,2], target = 8 输出：[[2,2,2,2]]
解释：只能选出四个 2，和为 8；不同下标的选法只算一个。
数据范围
1 <= nums.length <= 200-10^9 <= nums[i] <= 10^9-10^9 <= target <= 10^9
解题思路
在三数之和外面再套一层循环。先排序，用两重循环固定前两个数 nums[i]、nums[j]，再在 j 右侧用 lo、hi 夹逼：和偏小 lo 右移，偏大 hi 左移，相等就记录一组并同时收缩。去重靠排序：i、j 遇到和上一个相同的值就跳过；找到一组后 lo 跳过所有重复值。
为什么正确
每组 (i, j) 只用其值第一次出现的位置；在内层夹逼中，每种 (nums[lo], nums[hi]) 值对至多记录一次，所以答案不重复也不遗漏。
复杂度分析
时间 O(n³)：两层循环 O(n²) 乘以夹逼 O(n)；空间 O(log n)（排序），不计答案。
易错点
数值可达 ±10⁹，四数之和会超出 32 位整数，C++、Java 中要用 long 求和。j 的去重条件是 j > i + 1（不是 j > 0），否则会误跳 nums[j] == nums[i] 的合法组合，比如 [2,2,2,2]。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
nums.sort()
n, ans = len(nums), []
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
lo, hi = j + 1, n - 1
while lo < hi:
s = nums[i] + nums[j] + nums[lo] + nums[hi]
if s < target:
lo += 1
elif s > target:
hi -= 1
else:
ans.append([nums[i], nums[j], nums[lo], nums[hi]])
lo += 1
while lo < hi and nums[lo] == nums[lo - 1]:
lo += 1
hi -= 1
return ansclass Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
Arrays.sort(nums);
int n = nums.length; List<List<Integer>> ans = new ArrayList<>();
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 lo = j + 1, hi = n - 1;
while (lo < hi) {
long s = (long) nums[i] + nums[j] + nums[lo] + nums[hi];
if (s < target) {
lo++;
} else if (s > target) {
hi--;
} else {
ans.add(Arrays.asList(nums[i], nums[j], nums[lo], nums[hi]));
lo++;
while (lo < hi && nums[lo] == nums[lo - 1]) {
lo++;
}
hi--;
}
}
}
}
return ans;
}
}class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
sort(nums.begin(), nums.end());
int n = nums.size(); vector<vector<int>> ans;
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 lo = j + 1, hi = n - 1;
while (lo < hi) {
long long s = (long long)nums[i] + nums[j] + nums[lo] + nums[hi];
if (s < target) {
lo++;
} else if (s > target) {
hi--;
} else {
ans.push_back({nums[i], nums[j], nums[lo], nums[hi]});
lo++;
while (lo < hi && nums[lo] == nums[lo - 1]) {
lo++;
}
hi--;
}
}
}
}
return ans;
}
};func fourSum(nums []int, target int) [][]int {
sort.Ints(nums)
n, ans := len(nums), [][]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
}
lo, hi := j+1, n-1
for lo < hi {
s := nums[i] + nums[j] + nums[lo] + nums[hi]
if s < target {
lo++
} else if s > target {
hi--
} else {
ans = append(ans, []int{nums[i], nums[j], nums[lo], nums[hi]})
lo++
for lo < hi && nums[lo] == nums[lo-1] {
lo++
}
hi--
}
}
}
}
return ans
}var fourSum = function(nums, target) {
nums.sort((a, b) => a - b);
const n = nums.length, ans = [];
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 lo = j + 1, hi = n - 1;
while (lo < hi) {
const s = nums[i] + nums[j] + nums[lo] + nums[hi];
if (s < target) {
lo++;
} else if (s > target) {
hi--;
} else {
ans.push([nums[i], nums[j], nums[lo], nums[hi]]);
lo++;
while (lo < hi && nums[lo] === nums[lo - 1]) {
lo++;
}
hi--;
}
}
}
}
return ans;
};function fourSum(nums: number[], target: number): number[][] {
nums.sort((a, b) => a - b);
const n = nums.length, ans: number[][] = [];
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 lo = j + 1, hi = n - 1;
while (lo < hi) {
const s = nums[i] + nums[j] + nums[lo] + nums[hi];
if (s < target) {
lo++;
} else if (s > target) {
hi--;
} else {
ans.push([nums[i], nums[j], nums[lo], nums[hi]]);
lo++;
while (lo < hi && nums[lo] === nums[lo - 1]) {
lo++;
}
hi--;
}
}
}
}
return ans;
}