0167. Two Sum II - Input Array Is Sorted ======================================== 题目信息 -------- :题号: 0167. 两数之和 II - 输入有序数组 :难度: Medium :主题: 数组、二分查找、双指针 :原题: `LeetCode 0167 `_ :重点: 用当前最小值与最大值的和,一次排除以某个端点为成员的全部候选数对 题目重述 -------- 给定按非递减顺序排列的整数数组 ``numbers`` 和整数 ``target``,找出两个不同位置, 使其元素之和等于 ``target``。题目保证恰好存在一个答案。 返回 ``[index1, index2]``,下标从 1 开始,并满足 ``index1 < index2``;算法只能使用 常数级额外空间。 自建示例 -------- .. code-block:: text 输入:numbers = [1,2,4,6,10], target = 8 输出:[2,4] numbers[1] + numbers[3] = 2 + 6 = 8;返回一基下标 [2,4]。 .. code-block:: text 输入:numbers = [1,3,3,6], target = 6 输出:[2,3] 两个值都为 3,但来自两个不同位置。 .. code-block:: text 输入:numbers = [-8,-3,1,4,9], target = 6 输出:[2,5] 排序产生的单调关系对负数同样成立。 C++ 实现 -------- .. code-block:: cpp #include class Solution { private: std::vector binarySearchEachLeft( const std::vector& numbers, int target) { int size = static_cast(numbers.size()); for (int first = 0; first < size; ++first) { long long wanted = static_cast(target) - numbers[first]; int left = first + 1; int right = size - 1; while (left <= right) { int middle = left + (right - left) / 2; if (numbers[middle] == wanted) { return {first + 1, middle + 1}; } if (numbers[middle] < wanted) { left = middle + 1; } else { right = middle - 1; } } } return {}; } std::vector oppositePointers( const std::vector& numbers, int target) { int left = 0; int right = static_cast(numbers.size()) - 1; while (left < right) { long long sum = static_cast(numbers[left]) + numbers[right]; if (sum == target) { return {left + 1, right + 1}; } if (sum < target) { ++left; } else { --right; } } return {}; } public: std::vector twoSum( std::vector& numbers, int target) { return oppositePointers(numbers, target); } }; 题解 ---- 从数对枚举到补数搜索 ~~~~~~~~~~~~~~~~~~~~ 不利用有序性时,最直接的搜索空间是全部 ``i < j``,共有 ``n(n-1)/2`` 个数对。 固定第一个位置 ``i`` 后,第二个值必须等于 ``target - numbers[i]``,所以问题可以改写为 “在右侧寻找一个确定的补数”。 数组已经有序,``binarySearchEachLeft`` 能为每个 ``i`` 在后缀 ``[i+1,n)`` 中二分 查找补数,将时间从 ``O(n²)`` 降到 ``O(n log n)``。从 ``i+1`` 开始搜索还直接保证 两个位置不同、返回下标有序。 这个方案仍有重复工作:每换一个左位置,都会在大量重叠的后缀上重新二分。排序不仅能 回答“某个补数是否存在”,还允许一次比较排除以一个端点为成员的整组数对。 两端之和提供删除规则 ~~~~~~~~~~~~~~~~~~~~ 令 ``left``、``right`` 指向尚未排除区间的最小值和最大值。当前和有三种情况: * 若等于 ``target``,两个位置就是答案; * 若小于 ``target``,固定当前最小值 ``numbers[left]``,它与区间内任何元素之和都不 会超过 ``numbers[left] + numbers[right]``,所以全部过小。当前 ``left`` 不可能 参与答案,可以整体排除; * 若大于 ``target``,固定当前最大值 ``numbers[right]``,它与区间内任何元素之和都 不会低于 ``numbers[left] + numbers[right]``,所以全部过大。当前 ``right`` 不可能 参与答案,可以整体排除。 因此和过小时只移动左指针,和过大时只移动右指针。移动另一端会缺少排除依据,也可能 跳过唯一答案。 区间不变量与正确性 ~~~~~~~~~~~~~~~~~~ 循环开始时维护不变量:若答案尚未找到,则唯一答案的两个下标都位于闭区间 ``[left,right]`` 中。 初始区间包含整个数组,显然成立。当前和过小时,上述论证证明 ``left`` 无法与区间内 任何位置配对,所以删除它不会删除答案;和过大时同理可以安全删除 ``right``。每轮都让 区间缩小一个位置,并保持不变量。 题目保证答案存在,因此在 ``left < right`` 期间必会遇到目标和。条件 ``left < right`` 还保证不会把同一位置使用两次;重复数值不受影响,只要它们位于不同下标即可。 具体走读 ~~~~~~~~ 对 ``numbers = [1,2,4,6,10]``、``target = 8``: .. code-block:: text left right 端点值 和 结论 0 4 1,10 11 过大,10 不可能参与,right 左移 0 3 1,6 7 过小,1 不可能参与,left 右移 1 3 2,6 8 命中 最终零基下标是 1、3,接口要求一基下标,所以返回 ``[2,4]``。指针只在找到答案时转换 下标,内部推理始终使用 C++ 数组的零基位置。 数值与返回边界 ~~~~~~~~~~~~~~ ``sum`` 使用 ``long long``,避免两个 ``int`` 相加时先发生溢出;补数基线也在减法前 提升 ``target``。虽然题目保证存在答案,两个辅助方法仍保留空结果作为防御性出口。 主解不修改输入,也不建立哈希表或排序副本,满足常数额外空间要求。 方案选择与复杂度 ~~~~~~~~~~~~~~~~ 逐左端二分的时间复杂度为 ``O(n log n)``、额外空间为 ``O(1)``,它展示了从补数线性 搜索到有序查找的第一步优化。双指针进一步让两个端点全程单调移动,每个位置最多被排除 一次,时间为 ``O(n)``、额外空间为 ``O(1)``,因此 ``oppositePointers`` 是主解。