0018. 4Sum
==========
题目信息
--------
:题号: 0018. 四数之和
:难度: Medium
:主题: 数组、排序、双指针、去重
:原题: `LeetCode 0018 `_
:重点: 固定前两个值,把剩余问题降为有序两数之和,并在四个选择层级中直接消除重复结果
题目重述
--------
给定整数数组 ``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++ 实现
--------
.. code-block:: cpp
#include
#include
#include
class Solution {
private:
std::vector> enumerateFour(const std::vector& nums, int target) {
std::set> unique;
const int n = static_cast(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 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> sortAndTwoPointers(std::vector nums, int target) {
if (nums.size() < 4) {
return {};
}
std::sort(nums.begin(), nums.end());
std::vector> result;
const int n = static_cast(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> fourSum(std::vector& 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``。