Two Sum II – Input Array Is Sorted (167): Hash Map vs. Two Pointers on a Sorted Array【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode本篇文章围绕 LeetCode 第 167 题「两数之和 II - 输入有序数组」展开题目在有序数组上寻找和为 target 的两个数要求返回从 1 开始计数的下标。文章完整继承该题解的核心思路与 JS / C / Java / Python 四语言代码并结合本仓库的源码体系深入讲解哈希表与左右端点双指针两种解法、正确性证明、边界细节以及它作为「两数和 / N 数和」系列问题基石的地位帮助读者掌握有序数组上双指针的套路并加以复用。题目描述这是 LeetCode 头号题目 1. Two Sum两数之和 的第二个版本难度为简单。核心区别在于输入数组已按升序排列。给定一个已按照升序排列的有序数组找到两个数使得它们相加之和等于目标数。 函数应该返回这两个下标值 index1 和 index2其中 index1 必须小于 index2。 说明: - 返回的下标值index1 和 index2不是从零开始的。 - 你可以假设每个输入只对应唯一的答案而且你不可以重复使用相同的元素。 示例: 输入: numbers [2, 7, 11, 15], target 9 输出: [1, 2] 解释: 2 与 7 之和等于目标数 9。因此 index1 1, index2 2。两个容易踩坑的点值得单独强调下标从 1 开始数组第一个元素对应的 index 是 1而不是 0。代码中凡是返回位置的地方都需要做1偏移每个输入只有唯一答案不需要像 15. 三数之和那样处理重复三元组去重15. 3Sum 中因为有重复答案才需要额外的去重逻辑。前置知识双指针左右端点指针本仓库在 91/two-pointers.md 中系统性地总结了双指针思想双指针本质是两个指针协同遍历的算法思想常见题型被归纳为三类——快慢指针、左右端点指针、固定间距指针。其中「左右端点指针」的典型应用就是二分查找以及有序数组上的两数之和 / N 数之和系列问题。167 题正是左右端点指针最直接的入门例题// 左右端点指针模板摘自 91/two-pointers.md l 0 r n - 1 while l r if 找到了 return 找到的值 if 一定条件1 l 1 else if 一定条件2 r - 1 return 没找到本仓库中其它大量题目也复用同一套路如 11. 盛最多水的容器、125. 验证回文串、42. 接雨水 等读完本文后可以顺藤摸瓜继续练习。公司该题在互联网公司面试中高频出现本仓库记录中提到阿里、腾讯、百度、字节、amazon。思路一哈希表空间换时间由于题目并没有对空间复杂度提出要求一个最直接的思路是遍历数组的同时用哈希表记录已经访问过的数字及其下标每遇到一个新数字就查询target - element是否已经在哈希表中出现过。class Solution: def twoSum(self, numbers: List[int], target: int) - List[int]: visited {} for index, number in enumerate(numbers): if target - number in visited: return [visited[target-number], index1] else: visited[number] index 1这一思路与 1. 两数之和 完全一致——把「求和」问题转化为「求差」问题用哈希表把每次查找从 O(N) 降到 O(1)。值得注意的是哈希表解法其实根本不依赖数组有序因此即使输入是无序数组这一版代码依然正确。不过当题目对空间复杂度有要求时哈希表 O(N) 的空间就不再适用此时应当充分利用「数组已排序」这个额外条件改用双指针。思路二左右端点双指针最优解由于数组有序可以用一个 left 指针指向最左端一个 right 指针指向最右端两个指针向中间靠拢如果numbers[left] numbers[right] target直接返回[left 1, right 1]如果numbers[left] numbers[right] target说明当前和偏大需要减小和由于数组升序只有把 right 左移指向更小的数才能减小和如果numbers[left] numbers[right] target说明当前和偏小需要增大和只有把 left 右移指向更大的数才能增大和。如果数组无序则需要先排序从这里也可以看出排序是多么重要的操作。排序本身 O(N log N)在规模较大时优于暴力枚举 O(N²)相关讨论可见 15. 3Sum 中「排序后双指针」的思路。为什么双指针不会漏掉答案正确性直觉这是一个经常被追问的证明题。设最优解对应的位置为(i, j)i j。考察双指针的任意一个中间状态(l, r)若l i说明 left 指针还在最优左端点的左侧。此时若numbers[l] numbers[r] target算法会把r左移而r j始终成立right 指针从未越过最优右端点移动过程中一旦r到达jnumbers[l] numbers[j] numbers[i] numbers[j] target于是不会再继续左移 right最终 left 会一路推进到i对称地若r jright 指针会持续右移实际是左移直至j。因此无论中间过程如何双指针必然会在某个时刻同时命中(i, j)不会因贪心式移动而错过唯一解。各语言实现C 版class Solution { public: vectorint twoSum(vectorint numbers, int target) { int n numbers.size(); int left 0; int right n-1; while(left right) { if(numbers[left] numbers[right] target) { return {left 1, right 1}; } else if (numbers[left] numbers[right] target) { right--; } else { left; } } return {-1, -1}; } };Java 版class Solution { public int[] twoSum(int[] numbers, int target) { int n numbers.length; int left 0; int right n-1; while(left right) { if(numbers[left] numbers[right] target) { return new int[]{left 1, right 1}; } else if (numbers[left] numbers[right] target) { right--; } else { left; } } return new int[]{-1, -1}; } }Python 版class Solution: def twoSum(self, numbers: List[int], target: int) - List[int]: left, right 0, len(numbers) - 1 while left right: if numbers[left] numbers[right] target: left 1 if numbers[left] numbers[right] target: right - 1 if numbers[left] numbers[right] target: return [left1, right1]JS 版哈希表思路的完整实现/** * param {number[]} numbers * param {number} target * return {number[]} */ var twoSum function (numbers, target) { const visited {}; // 记录出现的数字空间复杂度 N for (let index 0; index numbers.length; index) { const element numbers[index]; if (visited[target - element] ! void 0) { return [visited[target - element], index 1]; } visited[element] index 1; } return []; };注意 JS 版中visited[target - element] ! void 0的判断正是利用了哈希表存储1-based下标index 1的设计——只有真正访问过的下标才会被记录从而避免与「值为 0 的元素」产生歧义。关键点解析有序是双指针的前提只有数组升序才能保证「和偏大时右移 right、和偏小时左移 left」这个移动策略单调有效求和转换为求差这是两数之和系列问题共同的切入点哈希表解法依赖此思想双指针解法同样适用返回 1-based 下标所有返回位置都需要1复杂度双指针解法下每次循环必定移动 left 或 right 其中之一两指针最多各移动 N 次即相遇因此只需一趟遍历。复杂度分析解法时间复杂度空间复杂度依赖有序哈希表$O(N)$$O(N)$否左右端点双指针$O(N)$$O(1)$是两种解法的时间复杂度均为 $O(N)$双指针将空间复杂度从 $O(N)$ 优化到 $O(1)$这正是「有序数组 双指针」组合的经典价值。从源码结构看双指针的更多细节while 边界left rightvsleft right题目保证存在唯一答案因此left right即可安全退出若使用在left right时会重复计算同一个元素恰好违反题目「不能重复使用相同元素」的约束。C/Java 版用left right同样能正确工作但要注意它依赖「一定有答案」的假设答案唯一意味着无需去重对比 15. 3Sum 的代码你会发现那里多出了大量while (nums[left] nums[left 1]) left;之类的跳过重复逻辑这正是两题在实现上的核心差异有序数组上的指针移动不止出现在求和场景本仓库的 88. 合并两个有序数组 使用从后往前的三指针原地合并空间 O(1)209. 长度最小的子数组 使用同向双指针滑动窗口它们共同构成「指针在有序/连续结构上移动」的完整家族可与本仓库的 91/two-pointers.md 分类框架相互印证。延伸167 题在「两数和 / N 数和」系列中的位置167 题可以看作有序数组上双指针的最小可运行模板后续更难的问题大多建立在其上从无序到有序1. 两数之和无序数组 哈希表O(N) 时间 / O(N) 空间→ 167有序数组 双指针O(N) 时间 / O(1) 空间从两数到三数15. 3Sum 将问题分治拆解为「固定一个数 剩余两数之和」剩余部分就是在有序数组上做 167 的双指针整体复杂度 O(N²)更多变体双指针模板还适用于 11. 盛最多水的容器同样从两端向中间收拢、125. 验证回文串首尾字符比较等题目。仓库对应的思路图取自 15. 3Sum直观展示了「排序 双指针」如何把 N 数和问题归约到两数之和此外仓库在 assets/drawio/11.container-with-most-water.drawio 等文件中提供了可编辑的双指针类题目标注图方便读者对照理解指针移动过程。小结167 题虽然难度为「简单」但它同时承载了三个重要的算法素养空间换时间的哈希表思想、有序数据上的双指针单调移动、以及将复杂问题归约到已解决问题分治。建议读者用本文的四语言代码各自跑通示例numbers [2, 7, 11, 15], target 9再尝试扩展输入如含负数、含重复元素、target 为负从而真正掌握「左右端点指针」这一高频套路。【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考