Two Sum II – Input Array Is Sorted (167): Hash Map vs. Two Pointers on a Sorted Array-迪斯科星球

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], index+1] 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到达j，numbers[l] + numbers[j] <= numbers[i] + numbers[j] = target，于是不会再继续左移 right，最终 left 会一路推进到i；
对称地，若r > j，right 指针会持续右移（实际是左移）直至j。

因此无论中间过程如何，双指针必然会在某个时刻同时命中(i, j)，不会因贪心式移动而错过唯一解。

各语言实现

C++ 版：

class Solution { public: vector<int> twoSum(vector<int>& 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 [left+1, right+1]

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 为负），从而真正掌握「左右端点指针」这一高频套路。

创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考

企业官网建设流程全解析