0015. 3Sum
==========
题目信息
--------
:题号: 0015. 三数之和
:难度: Medium
:主题: 数组、排序、双指针、去重
:原题: `LeetCode 0015 `_
:重点: 固定首值把三数搜索降为两数搜索,再用有序性排除候选,并在生成答案时完成数值去重
题目重述
--------
给定整数数组 ``nums``,找出所有满足 ``i``、``j``、``k`` 两两不同且
``nums[i] + nums[j] + nums[k] == 0`` 的三元组。
结果按数值组合去重:即使同一组三个数可以由不同下标组成,也只能返回一次。三元组之间的顺序以及每个
三元组内部的顺序都不作要求。数组长度位于 ``[3, 3000]``,元素位于 ``[-10^5, 10^5]``。
自建示例
--------
* 多组答案:``nums = [-4, -1, -1, 0, 1, 2, 3]``,返回 ``[-4, 1, 3]``、``[-1, -1, 2]``、
``[-1, 0, 1]``;
* 重复下标组合:``nums = [0, 0, 0, 0]``,只返回一个 ``[0, 0, 0]``;
* 允许重复数值:``nums = [-2, 1, 1]``,两个 ``1`` 来自不同下标,返回 ``[-2, 1, 1]``;
* 没有答案:``nums = [2, 4, 7, 9]``,返回空集合;
* 最小规模:``nums = [-1, 0, 1]``,返回 ``[-1, 0, 1]``。
C++ 实现
--------
.. code-block:: cpp
#include
#include
#include
#include
class Solution {
private:
std::vector> enumerateTriples(const std::vector& nums) {
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) {
if (1LL * nums[first] + nums[second] + nums[third] != 0) {
continue;
}
std::vector triple{nums[first], nums[second], nums[third]};
std::sort(triple.begin(), triple.end());
unique.insert(triple);
}
}
}
return {unique.begin(), unique.end()};
}
std::vector> hashAfterFixingFirst(const std::vector& nums) {
std::set> unique;
const int n = static_cast(nums.size());
for (int first = 0; first < n; ++first) {
std::unordered_set seen;
for (int second = first + 1; second < n; ++second) {
const int need = -nums[first] - nums[second];
if (seen.count(need)) {
std::vector triple{nums[first], nums[second], need};
std::sort(triple.begin(), triple.end());
unique.insert(triple);
}
seen.insert(nums[second]);
}
}
return {unique.begin(), unique.end()};
}
std::vector> sortAndTwoPointers(std::vector nums) {
std::sort(nums.begin(), nums.end());
std::vector> result;
const int n = static_cast(nums.size());
for (int first = 0; first + 2 < n; ++first) {
if (first > 0 && nums[first] == nums[first - 1]) {
continue;
}
if (1LL * nums[first] + nums[first + 1] + nums[first + 2] > 0) {
break;
}
if (1LL * nums[first] + nums[n - 2] + nums[n - 1] < 0) {
continue;
}
int left = first + 1;
int right = n - 1;
while (left < right) {
const long long sum = 1LL * nums[first] + nums[left] + nums[right];
if (sum < 0) {
++left;
} else if (sum > 0) {
--right;
} else {
result.push_back({nums[first], 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> threeSum(std::vector& nums) {
return sortAndTwoPointers(nums);
}
};
题解
----
三重枚举
~~~~~~~~
最直接的方法使用三个递增下标枚举全部组合。候选数量为 ``O(n³)``,并且同一个数值三元组可能由多组下标
重复产生。
``enumerateTriples`` 在命中后先把三个值排序,再放入有序集合。排序统一三元组内部顺序,集合负责删除重复
结果。这种方法完整但代价很高:搜索和去重彼此独立,算法无法在枚举过程中利用已经知道的数值关系。
固定首值
~~~~~~~~
固定第一个数 ``nums[first]`` 后,问题变为在其后方寻找两个数,使它们满足:
``nums[second] + nums[third] = -nums[first]``。
于是三数搜索被拆成 ``n`` 次两数之和。``hashAfterFixingFirst`` 对每个首下标扫描一次后缀,并用 ``seen``
查询当前元素所需的补数,期望时间降为 ``O(n²)``。
哈希表只解决“补数是否已经出现”,并未自然统一三元组的数值顺序。不同首下标和不同后缀位置仍可能产生
同一组三个值,所以该方法仍需要排序每个命中并使用集合去重。
排序后的搜索方向
~~~~~~~~~~~~~~~~
若先把数组排序,固定 ``first`` 后,后缀中的两数问题具有单调性。令 ``left`` 指向最小候选,``right``
指向最大候选:
* 总和小于零,需要增大和值,只能右移 ``left``;
* 总和大于零,需要减小和值,只能左移 ``right``;
* 总和等于零,记录三元组,并让两侧都越过本次已经使用的重复值。
当总和小于零时,当前 ``right`` 已是可用的最大右值。固定 ``left``,改用任何更小的右值只会使总和更小,
不可能等于零,所以当前左值可以删除。总和大于零时论证对称:当前 ``left`` 已是可用的最小左值,固定
``right`` 后改用任何更大的左值只会使总和更大,因此当前右值可以删除。
每次移动都排除一整组不可能组合,两个指针不需要回退。
三处去重
~~~~~~~~
排序后,每个命中的三元组已经按非降顺序排列,不再需要单独排序结果。重复值也集中在连续区间中。
第一处去重发生在 ``first``。若当前首值与前一个首值相同,前一个位置拥有更大的后缀搜索范围,并且已经检查
过当前首值能够形成的全部数值组合,所以当前整轮可以跳过。
另外两处发生在命中之后。代码先记录当前三元组,再分别移动 ``left`` 和 ``right`` 一格;随后越过与刚刚
使用值相同的连续元素。这些位置只会再次生成完全相同的三元组,跳过它们不会删除新的数值组合。
重复值也可以采用其他正确的跳过时机,关键不在“必须命中后才能跳”,而在于每个不同的候选值至少保留一次,
并且不能让指针停留在已经记录的同一数值对上。
边界剪枝
~~~~~~~~
固定 ``first`` 后,可以在进入双指针循环前计算本轮可能达到的最小和与最大和。
若 ``nums[first] + nums[first + 1] + nums[first + 2] > 0``,当前最小三数和已经为正,后续首值只会更大,
所以整个外层循环可以结束。
若 ``nums[first] + nums[n - 2] + nums[n - 1] < 0``,当前首值即使搭配数组中最大的两个后缀值仍然偏小,
本轮不可能产生答案,可以直接处理下一个首值。
剪枝只减少实际扫描量,不改变最坏 ``O(n²)`` 时间复杂度。
代码对应
~~~~~~~~
``enumerateTriples`` 中三个下标都未知,因此需要三层循环和结果集合。
``hashAfterFixingFirst`` 固定首下标,把第三层循环替换为补数查询,但仍保留哈希表与结果集合。
``sortAndTwoPointers`` 进一步用排序替换哈希状态:和值方向决定删除哪一侧,连续重复值直接在指针移动时跳过,
结果集合随之消失。公开入口采用该方法,并通过值传递排序副本,不修改调用者的原数组。
复杂度分析
~~~~~~~~~~
.. list-table::
:header-rows: 1
* - 方法
- 时间复杂度
- 工作空间
* - 三重枚举
- ``O(n³)``
- 取决于去重集合
* - 固定首值加哈希
- 期望 ``O(n²)``
- ``O(n)`` 加去重集合
* - 排序双指针
- ``O(n²)``
- ``O(n)`` 输入副本
排序需要 ``O(n log n)``,被双指针的 ``O(n²)`` 主过程覆盖。三数和使用 ``long long`` 计算;返回结果空间
不计入工作空间。