0015. 3Sum¶
题目信息¶
- 题号:
三数之和
- 难度:
Medium
- 主题:
数组、排序、双指针、去重
- 原题:
- 重点:
固定首值把三数搜索降为两数搜索,再用有序性排除候选,并在生成答案时完成数值去重
题目重述¶
给定整数数组 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++ 实现¶
#include <algorithm>
#include <set>
#include <unordered_set>
#include <vector>
class Solution {
private:
std::vector<std::vector<int>> enumerateTriples(const std::vector<int>& nums) {
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) {
if (1LL * nums[first] + nums[second] + nums[third] != 0) {
continue;
}
std::vector<int> triple{nums[first], nums[second], nums[third]};
std::sort(triple.begin(), triple.end());
unique.insert(triple);
}
}
}
return {unique.begin(), unique.end()};
}
std::vector<std::vector<int>> hashAfterFixingFirst(const std::vector<int>& nums) {
std::set<std::vector<int>> unique;
const int n = static_cast<int>(nums.size());
for (int first = 0; first < n; ++first) {
std::unordered_set<int> seen;
for (int second = first + 1; second < n; ++second) {
const int need = -nums[first] - nums[second];
if (seen.count(need)) {
std::vector<int> 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<std::vector<int>> sortAndTwoPointers(std::vector<int> nums) {
std::sort(nums.begin(), nums.end());
std::vector<std::vector<int>> result;
const int n = static_cast<int>(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<std::vector<int>> threeSum(std::vector<int>& 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 进一步用排序替换哈希状态:和值方向决定删除哪一侧,连续重复值直接在指针移动时跳过,
结果集合随之消失。公开入口采用该方法,并通过值传递排序副本,不修改调用者的原数组。
复杂度分析¶
方法 |
时间复杂度 |
工作空间 |
|---|---|---|
三重枚举 |
|
取决于去重集合 |
固定首值加哈希 |
期望 |
|
排序双指针 |
|
|
排序需要 O(n log n),被双指针的 O(n²) 主过程覆盖。三数和使用 long long 计算;返回结果空间
不计入工作空间。