LeetCode-Book 精讲：167. 两数之和 II（输入有序数组）双指针解法与正确性证明

LeetCode-Book 精讲167. 两数之和 II输入有序数组双指针解法与正确性证明【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book本篇是 LeetCode-Book 仓库中 selected_coding_interview/docs/167. 两数之和 II.md 的深度解读。题目要求在已按非递减顺序排序的数组numbers中找出和为target的两个数并返回从 1 开始计数的下标。文章将以原文档为核心梳理 HashMap 与对撞双指针两种思路的取舍完整给出算法流程、正确性证明以及 Python / Java / C 三语言实现并结合仓库中 lc_167_two_sum_ii.py 等源码文件让读者既能看懂怎么解也能理解为什么这样解是对的。题目回顾与两种候选思路本题是 LeetCode 经典题 1. 两数之和 的进阶版本核心差异在于输入数组numbers已按非递减顺序升序排序返回的下标要求从 1 开始计数即数组中的第 1 个元素对应返回下标1。思路一HashMap 哈希表法沿用经典题的做法借助哈希表记录值 → 下标的映射在遍历数组的同时查找target - numbers[i]是否已经出现过。时间复杂度$O(N)$只需一次遍历空间复杂度$O(N)$需要额外的哈希表存储映射关系。思路二对撞双指针法本题推荐原文档明确指出由于numbers是排序数组因此可使用双指针法将空间复杂度降低至 $O(1)$。这是本题与经典版两数之和最本质的区别——排序性质让夹逼成为可能从而免去哈希表的额外空间开销。对比项HashMap 法对撞双指针法是否利用排序性质否是时间复杂度$O(N)$$O(N)$空间复杂度$O(N)$$O(1)$适用场景任意无序数组仅限已排序数组从源码结构看仓库在 Python、Java、C 三种语言中都采用了双指针方案作为本题的标准实现这也印证了它在面试中的推荐地位。算法流程对撞双指针的夹逼搜索原文档将算法流程划分为三个步骤这里结合仓库源码逐条展开。1. 初始化双指针指向数组两端指针i指向数组左端指针j指向数组右端即所谓的对撞双指针i 0j len(numbers) - 1在仓库的 Python 实现 lc_167_two_sum_ii.py 中对应i, j 0, len(numbers) - 12. 循环搜索按和的大小收缩指针循环条件为while i j即双指针相遇时跳出。每次迭代计算当前和$s numbers[i] numbers[j]$若 $s target$说明整体和偏大需要减小而左指针已经是当前区间最小值唯一可行的是让右指针向左移动执行 $j j - 1$若 $s target$说明整体和偏小需要增大让左指针向右移动执行 $i i 1$若 $s target$由于题目要求索引从 1 开始返回数组[i 1, j 1]。3. 循环结束返回空结果若双指针相遇仍未找到目标组合返回空数组代表数组中不存在和为target的两个数。仓库源码对照Python 版完整实现lc_167_two_sum_ii.pyclass Solution: def twoSum(self, numbers: List[int], target: int) - List[int]: i, j 0, len(numbers) - 1 while i j: s numbers[i] numbers[j] if s target: j - 1 elif s target: i 1 else: return i 1, j 1 return []Java 版实现lc_167_two_sum.javaclass Solution { public int[] twoSum(int[] numbers, int target) { int i 0, j numbers.length - 1; while (i j) { int s numbers[i] numbers[j]; if (s target) i; else if (s target) j--; else return new int[] { i 1, j 1 }; } return new int[0]; } }C 版实现lc_167_two_sum_ii_input_array_is_sorted_s1.cppclass Solution { public: vectorint twoSum(vectorint numbers, int target) { int i 0, j numbers.size() - 1; while (i j) { int s numbers[i] numbers[j]; if (s target) i; else if (s target) j--; else return { i 1, j 1 }; } return {}; } };三份代码的循环逻辑完全一致仅语法层面有差异Java/C 对先判断小于再判断大于的顺序与 Python 版略有不同但语义等价不影响正确性。正确性证明为什么指针移动不会漏掉解对撞双指针最容易引起疑虑的问题是每次只移动一个指针会不会把可能的解跳过去原文档用状态集合消去法给出了严谨证明这里完整展开。状态表示记每个候选状态为 $S(i, j) numbers[i] numbers[j]$其中 $i j$。算法的每一步都处在某个状态上并根据 $S(i, j)$ 与 $target$ 的大小关系决定迁移方向。关键引理移动 $i$ 是安全的假设当前状态满足 $S(i, j) target$算法执行 $i i 1$状态切换至 $S(i 1, j)$。这一步操作消去了一行元素即一次性排除了如下状态集合$${S(i, i1),\ S(i, i2),\ \dots,\ S(i, j-2),\ S(i, j-1),\ S(i, j)}$$由于双指针始终向中间收缩被消去的这些状态固定左端为 $i$、右端在 $i1$ 到 $j$ 之间的所有组合之后不可能再被访问到。为什么消去的状态都不可能是解因为numbers是排序数组对集合中的任意状态 $S(i, k)$其中 $i k \le j$都有$$S(i, k) numbers[i] numbers[k] \le numbers[i] numbers[j] S(i, j) target$$也就是说这些被消去的状态的和都严格小于 $target$它们全部不是解。因此指针 $i$ 的移动操作不会导致解的丢失得证——移动 $i$ 是安全的。对称论证与最终结论同理若 $S(i, j) target$执行 $j j - 1$ 时会消去一列元素 ${S(i, j),\ S(i1, j),\ \dots,\ S(j-1, j)}$由于数组升序这些状态的和都严格大于 $target$同样不可能是解因此指针 $j$ 的移动也是安全的。结论每一步指针移动都只排除了必然不是解的状态解的集合始终被完整保留当双指针相遇时要么已经返回目标组合要么可确定无解。因此对撞双指针法是正确且完备的。这一证明思路单调性 状态集合消去不仅适用于本题也是后续 15. 三数之和、盛最多水的容器等排序 双指针题型的通用论证框架。复杂度分析时间复杂度 $O(N)$$N$ 为数组numbers的长度两个指针分别从左端、右端出发向中间靠拢整个过程指针i与指针j合计移动不超过 $N$ 次即双指针共同线性遍历整个数组。空间复杂度 $O(1)$仅使用i、j、s等常数个变量不随输入规模增长相比 HashMap 法的 $O(N)$ 空间有质的提升。仓库中的测试用例与运行方式仓库为本题配套了可直接运行的驱动代码便于读者验证实现。Python 测试驱动lc_167_two_sum_ii.py 末尾自带了测试用例test_input_numbers [2, 7, 11, 15] test_input_target 9 expected_output [1, 2] slt Solution() result slt.twoSum(test_input_numbers, test_input_target) print(result)以[2, 7, 11, 15]、target 9为例指针初始指向2和15和为17 9右指针左移指向11和为13 9继续左移指向7此时2 7 9返回[1, 2]。执行python3 selected_coding_interview/codes/python/lc_167_two_sum_ii.py即可看到输出(1, 2)。C 测试驱动C 版本lc_167_two_sum_ii_input_array_is_sorted_s1.cpp在main()中构造相同用例并通过PrintUtil::printVector(res)打印结果编译运行即可验证。Java 测试驱动Java 版本lc_167_two_sum.java同样内置了test_input_numbers {2, 7, 11, 15}、test_input_target 9、expected_output {1, 2}的驱动代码。值得一提的是仓库根目录的 fix_tests.py 中记录了lc_167_two_sum_ii的用例修复记录早期版本测试调用缺少target参数已统一修正为slt.twoSum([2,7,11,15], 9)这从侧面说明仓库对测试用例必须可运行、结果必须可复现的重视。边界情况与易错点下标从 1 开始返回[i 1, j 1]而非[i, j]这是本题与经典两数之和的最大差异也是最常见的扣分点。不存在解当双指针相遇i j仍无匹配时必须返回空数组/空列表而不是抛出异常或返回错误下标。不能重复使用同一元素i与j始终满足i j天然规避了同一个数使用两次的非法情况。数组升序是前提双指针法依赖排序性质才能保证消去的状态必不是解若输入未排序本方法失效只能退回 HashMap 法。小结本题的价值在于揭示了一个通用规律当题目给出有序数组这一附加条件时往往意味着可以将空间复杂度从 $O(N)$ 优化到 $O(1)$。从 HashMap 到对撞双指针算法流程看似简单三行循环但其背后的状态集合消去 单调性保证不丢解证明才是面试官真正考察的思维能力。建议读者结合 selected_coding_interview/docs/167. 两数之和 II.md 原文与仓库三语言源码反复推演并将此思路迁移到三数之和、四数之和、盛最多水的容器等同族题目中。【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考