0015. 3Sum

题目信息

题号:
  1. 三数之和

难度:

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++ 实现

#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³)

取决于去重集合

固定首值加哈希

期望 O(n²)

O(n) 加去重集合

排序双指针

O(n²)

O(n) 输入副本

排序需要 O(n log n),被双指针的 O(n²) 主过程覆盖。三数和使用 long long 计算;返回结果空间 不计入工作空间。