0016. 3Sum Closest ================== 题目信息 -------- :题号: 0016. 最接近的三数之和 :难度: Medium :主题: 数组、排序、双指针 :原题: `LeetCode 0016 `_ :重点: 固定一个数后,用有序和值与目标的大小关系排除一整组数对,并持续保存距离最小的和值 题目重述 -------- 给定整数数组 ``nums`` 和整数 ``target``,选择三个不同下标,返回与 ``target`` 最接近的三数之和。 接近程度由 ``abs(sum - target)`` 衡量。题目保证最近和值唯一。返回的是三数之和本身,不是下标、三元组或 最小距离。 数组长度位于 ``[3, 500]``,元素位于 ``[-1000, 1000]``,``target`` 位于 ``[-10^4, 10^4]``。 三数之和与距离都可以由 32 位有符号整数安全保存。 自建示例 -------- * 无法精确命中:``nums = [-5, -1, 2, 6, 9]``、``target = 4``,最近和值为 ``3``; * 精确命中:``nums = [7, -2, 4, 1]``、``target = 6``,三元组 ``[-2, 1, 7]`` 的和为 ``6``; * 全部为负:``nums = [-8, -5, -3, -1]``、``target = -10``,最近和值为 ``-9``; * 目标远大于全部和值:``nums = [1, 2, 5, 8]``、``target = 100``,最大三数之和 ``15`` 最近; * 最小规模:``nums = [-3, 2, 7]``、``target = 1``,唯一三数之和为 ``6``。 C++ 实现 -------- .. code-block:: cpp #include #include #include class Solution { private: int enumerateTriples(const std::vector& nums, int target) { int best = nums[0] + nums[1] + nums[2]; 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) { const int sum = nums[first] + nums[second] + nums[third]; if (std::abs(sum - target) < std::abs(best - target)) { best = sum; } } } } return best; } int sortAndTwoPointers(std::vector nums, int target) { std::sort(nums.begin(), nums.end()); int best = nums[0] + nums[1] + nums[2]; const int n = static_cast(nums.size()); for (int first = 0; first + 2 < n; ++first) { int left = first + 1; int right = n - 1; while (left < right) { const int sum = nums[first] + nums[left] + nums[right]; if (std::abs(sum - target) < std::abs(best - target)) { best = sum; } if (sum < target) { ++left; } else if (sum > target) { --right; } else { return target; } } } return best; } public: int threeSumClosest(std::vector& nums, int target) { return sortAndTwoPointers(nums, target); } }; 题解 ---- 三重枚举 ~~~~~~~~ 三个递增下标共有 ``O(n³)`` 种组合。``enumerateTriples`` 逐个计算和值,并在当前距离严格更小时替换 ``best``。题目保证最近和值唯一,所以不需要定义距离相等时的额外选择规则。 暴力法已经给出完整答案条件:算法不必保存三元组,只需维护“目前距离目标最近的和值”。需要优化的是候选组合 数量,而不是答案状态。 固定首值 ~~~~~~~~ 数组排序后固定 ``nums[first]``,剩余问题是在有序后缀中选择两个数,使 ``nums[left] + nums[right]`` 尽量接近 ``target - nums[first]``。 令 ``left = first + 1``、``right = n - 1``。在固定 ``first`` 时: * 右移 ``left``,和值不会减小; * 左移 ``right``,和值不会增大。 和值相对于目标的位置因此直接决定了唯一有意义的移动方向。 和值偏小 ~~~~~~~~ 若当前 ``sum < target``,固定 ``first`` 和 ``left``,再选择任意更小的右端 ``k < right``,有: ``nums[first] + nums[left] + nums[k] <= sum < target``。 这些和值都位于目标左侧,并且不大于已经检查的 ``sum``,所以它们到目标的距离不会更小。当前候选记录后, 所有使用当前 ``left`` 与更小右端的组合都可以排除,只需右移 ``left``,尝试把和值提高。 和值偏大 ~~~~~~~~ 若当前 ``sum > target``,固定 ``first`` 和 ``right``,再选择任意更大的左端 ``k > left``,有: ``nums[first] + nums[k] + nums[right] >= sum > target``。 这些和值都位于目标右侧,并且不小于已经检查的 ``sum``,同样不可能更接近目标。于是可以排除当前 ``right`` 与所有更大左端组成的组合,并左移 ``right``,尝试降低和值。 更新顺序 ~~~~~~~~ 当前和值无论偏小还是偏大,都可能是全局最近答案。因此每轮必须先比较 ``abs(sum - target)`` 与 ``abs(best - target)``,再移动指针。 指针移动的证明依赖“当前边界和值已经记录”:被排除的组合不会优于当前和值,而当前和值本身已经进入 ``best`` 的比较。若先移动,可能永久跳过这一边界候选。 搜索不变量 ~~~~~~~~~~ 固定 ``first`` 后,每轮开始时,尚未检查且仍可能优于 ``best`` 的数对都位于闭区间 ``[left, right]`` 中。 每轮先记录当前边界数对,再依据单调性删除一整组不可能更优的组合。指针相遇时,该首值对应的全部潜在更优 数对都已检查或被支配。外层遍历所有 ``first`` 后,``best`` 就是全局最近和值。 精确命中 ~~~~~~~~ 当 ``sum == target`` 时,距离为 ``0``。绝对距离不可能小于零,因此当前和值已经达到理论最优,可以立即返回 ``target``。 代码演进 ~~~~~~~~ ``enumerateTriples`` 使用三层循环显式选择三个下标,每个候选独立比较距离。 ``sortAndTwoPointers`` 固定首值后,用排序建立和值的单调变化。第三层枚举被两个只向中间移动的指针替代; 一次比较即可排除当前左端或右端参与的一整组候选。 公开入口采用 ``sortAndTwoPointers``。它接收输入副本进行排序,不会改变调用者传入的数组。 复杂度分析 ~~~~~~~~~~ .. list-table:: :header-rows: 1 * - 方法 - 时间复杂度 - 工作空间 - 主要代价 * - 三重枚举 - ``O(n³)`` - ``O(1)`` - 检查全部三下标组合 * - 排序双指针 - ``O(n²)`` - ``O(n)`` - 排序副本后,每个首值执行一次线性双指针扫描 排序耗时 ``O(n log n)``,被 ``O(n²)`` 的双指针阶段主导。工作空间中的 ``O(n)`` 来自输入副本;不计返回值。