0018. 4Sum¶
题目信息¶
- 题号:
四数之和
- 难度:
Medium
- 主题:
数组、排序、双指针、去重
- 原题:
- 重点:
固定前两个值,把剩余问题降为有序两数之和,并在四个选择层级中直接消除重复结果
题目重述¶
给定整数数组 nums 和整数 target,选择四个两两不同的下标,使对应元素之和等于 target,返回
所有不重复的数值四元组。
去重针对数值组合:相同四个值即使来自不同下标,也只能返回一次。结果中四元组的顺序以及四元组内部顺序均不
作要求。数组长度位于 [1, 200],元素和 target 位于 [-10^9, 10^9]。四个元素之和可能超出
32 位有符号整数范围,求和与剪枝边界必须使用 64 位整数。
自建示例¶
多组结果:
nums = [-3, -2, -1, 0, 0, 1, 2, 3]、target = 0,答案包含[-3, -2, 2, 3]、[-3, 0, 1, 2]、[-1, 0, 0, 1]等八组四元组;大量重复下标:
nums = [2, 2, 2, 2, 2]、target = 8,只返回[2, 2, 2, 2];元素不足:
nums = [1, 2, 3]、target = 6,返回空集合;无合法结果:
nums = [1, 2, 4, 8]、target = 20,返回空集合;需要 64 位求和:
nums = [1000000000, 1000000000, -1000000000, -1000000000]、target = 0, 返回[-1000000000, -1000000000, 1000000000, 1000000000]。
C++ 实现¶
#include <algorithm>
#include <set>
#include <vector>
class Solution {
private:
std::vector<std::vector<int>> enumerateFour(const std::vector<int>& nums, int target) {
std::set<std::vector<int>> unique;
const int n = static_cast<int>(nums.size());
for (int first = 0; first < n; ++first) {
for (int second = first + 1; second < n; ++second) {
for (int third = second + 1; third < n; ++third) {
for (int fourth = third + 1; fourth < n; ++fourth) {
const long long sum =
1LL * nums[first] + nums[second] + nums[third] + nums[fourth];
if (sum != target) {
continue;
}
std::vector<int> quadruplet{
nums[first], nums[second], nums[third], nums[fourth]
};
std::sort(quadruplet.begin(), quadruplet.end());
unique.insert(quadruplet);
}
}
}
}
return {unique.begin(), unique.end()};
}
std::vector<std::vector<int>> sortAndTwoPointers(std::vector<int> nums, int target) {
if (nums.size() < 4) {
return {};
}
std::sort(nums.begin(), nums.end());
std::vector<std::vector<int>> result;
const int n = static_cast<int>(nums.size());
const long long targetValue = target;
for (int first = 0; first + 3 < n; ++first) {
if (first > 0 && nums[first] == nums[first - 1]) {
continue;
}
const long long smallestFirst =
1LL * nums[first] + nums[first + 1] + nums[first + 2] + nums[first + 3];
if (smallestFirst > targetValue) {
break;
}
const long long largestFirst =
1LL * nums[first] + nums[n - 3] + nums[n - 2] + nums[n - 1];
if (largestFirst < targetValue) {
continue;
}
for (int second = first + 1; second + 2 < n; ++second) {
if (second > first + 1 && nums[second] == nums[second - 1]) {
continue;
}
const long long smallestSecond =
1LL * nums[first] + nums[second] + nums[second + 1] + nums[second + 2];
if (smallestSecond > targetValue) {
break;
}
const long long largestSecond =
1LL * nums[first] + nums[second] + nums[n - 2] + nums[n - 1];
if (largestSecond < targetValue) {
continue;
}
int left = second + 1;
int right = n - 1;
while (left < right) {
const long long sum =
1LL * nums[first] + nums[second] + nums[left] + nums[right];
if (sum < targetValue) {
++left;
} else if (sum > targetValue) {
--right;
} else {
result.push_back({nums[first], nums[second], nums[left], nums[right]});
++left;
--right;
while (left < right && nums[left] == nums[left - 1]) {
++left;
}
while (left < right && nums[right] == nums[right + 1]) {
--right;
}
}
}
}
}
return result;
}
public:
std::vector<std::vector<int>> fourSum(std::vector<int>& nums, int target) {
return sortAndTwoPointers(nums, target);
}
};
题解¶
四重枚举¶
四个递增下标形成 O(n⁴) 个候选。enumerateFour 检查全部组合,命中后还要把四个值排序并放入集合,
因为不同下标组合可能产生同一个数值四元组。
这个方法同时暴露了两个问题:最后两个下标仍被平方枚举,重复结果只能在生成之后交给集合处理。排序可以同时为 候选排除和按值去重提供结构。
固定前两项¶
排序后固定 nums[first] 和 nums[second],剩余条件变为:
nums[left] + nums[right] = target - nums[first] - nums[second]。
因此每一对固定值都对应一个有序两数之和问题。初始令 left = second + 1、right = n - 1:
当前四数和小于目标时,需要增大和值,只能右移
left;当前四数和大于目标时,需要减小和值,只能左移
right;当前四数和等于目标时,记录结果并同时移动两侧。
若当前和偏小,固定 left 并选择任何更靠左的右端,只会得到不大于当前值的和,因此这些组合不可能命中;
和偏大时论证对称。一次双指针扫描便覆盖固定前两项后的全部不同值对。
四处去重¶
排序使相同值连续出现,重复结果可以在选择发生的位置直接消除。
first 与前一位置同值时,它能够形成的所有数值四元组已经由前一个相同首值完整搜索,所以跳过。固定
first 后,second 也只保留该区间内相同值的第一次出现。
命中后先执行 ++left 和 --right,再跨过与刚使用值相同的连续元素。这样当前左右值组合只输出一次,
同时不会阻止下一组不同左右值继续参与搜索。四个数值层级都完成去重后,不再需要结果集合。
边界剪枝¶
固定 first 后,当前可组成的最小四数和为:
nums[first] + nums[first + 1] + nums[first + 2] + nums[first + 3]。
若它已经大于目标,更后的首值只会更大,外层可以直接结束。当前首值与最大的三个可用值之和仍小于目标时, 本轮不可能成功,只需处理下一个首值。
固定 second 后使用相同逻辑:与后面最小两个值组成的和过大时结束第二层;与全局最大两个值组成的和仍
过小时跳过当前第二值。剪枝不改变最坏复杂度,但会删除整段不可能区间。
搜索不变量¶
进入每次双指针循环时,当前 first、second 下尚未检查的候选全部位于 [left, right]。和值偏小
时删除当前左值及其与区间内所有右值形成的不可能组合;和值偏大时删除当前右值及其全部左侧组合;命中时记录
当前组合并仅跳过相同数值。
因此每次移动都只删除已经证明不可能命中或只会重复输出的候选,所有唯一四元组都会被记录一次。
代码演进¶
enumerateFour 使用四层循环选择四个未知下标,时间为 O(n⁴),并依赖集合去重。
sortAndTwoPointers 固定前两个下标后,用双指针替换后两层循环;排序又把集合去重替换为四个选择位置上的
重复值跳过。最小和与最大和判断进一步排除整段固定值范围。
公开入口采用 sortAndTwoPointers。辅助方法接收数组副本,因此排序不会修改调用者传入的 nums。
复杂度分析¶
排序耗时 O(n log n)。前两个固定位置形成 O(n²) 级别状态,每个状态的双指针总共移动 O(n),
因此总时间复杂度为 O(n³)。
优化方法因复制输入使用 O(n) 工作空间;若允许原地排序,则除排序栈外可视为 O(1)。返回结果空间不计
入工作空间。四数和、目标比较和所有剪枝边界均使用 long long。