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`` 计算;返回结果空间 不计入工作空间。