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``。