Leetcode Hot 100 开刷，第一站就来到这位算法圈老熟人：两数之和。
这题名气很大，面试里常见，刷题时也常被拿来当热身题。看着像开胃菜，实际上很适合拿来练两种经典思路：
- 排序 + 相向双指针
- 哈希表一次遍历
一道题，两种路子。 一个偏套路拆解，一个偏效率直给。 都值得记，别让它白来。
题目链接
题目描述
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那两个整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案，且同一个元素不能重复使用。
解法一：排序后使用相向双指针
这题最经典的做法其实是哈希表，一遍遍历直接找补数，时间复杂度可以做到 O(n)。
不过我先写的是另一种也很值得掌握的思路：
先保留每个元素的原始下标，再按数值排序，然后用左右双指针向中间逼近。
因为双指针一般要求数组有序，所以我们不能直接在原数组上左右夹击。 如果直接排序，原始下标又会丢失，所以要先把每个元素包装成：
[数值, 原下标]比如：
nums = [2, 7, 11, 15]target = 9预处理后会变成：
[[2, 0], [7, 1], [11, 2], [15, 3]]这样就算后面排序了，也还能通过第二项拿回原数组下标。
代码实现
class Solution(object): def twoSum(self, nums, target): """ :type nums: List[int] :type target: int :rtype: List[int] """ tmp_nums = [[i, idx] for idx, i in enumerate(nums)]
# 排序后使用双指针 tmp_nums = sorted(tmp_nums, key=lambda x: x[0]) n = len(nums) left, right = 0, n - 1
while left < right: x = tmp_nums[left][0] + tmp_nums[right][0] if x > target: right -= 1 elif x < target: left += 1 else: return [tmp_nums[left][1], tmp_nums[right][1]]
return [-1, -1]思路解析
双指针的核心逻辑很朴素：
- 如果当前两数之和 大于
target，说明和太大了，右指针左移 - 如果当前两数之和 小于
target，说明和太小了，左指针右移 - 如果刚好等于
target，直接返回这两个数对应的原始下标
拿样例来说：
nums = [2, 7, 11, 15]target = 9排序后：
[[2, 0], [7, 1], [11, 2], [15, 3]]初始时：
left = 0，指向2right = 3，指向15
先算：
2 + 15 = 17 > 9和太大，右指针左移。
再算：
2 + 11 = 13 > 9还是太大，右指针继续左移。
再来：
2 + 7 = 9命中目标，返回原始下标：
[0, 1]为什么这种方法可行
因为排序之后，数组具备了单调性。
设当前和为：
tmp_nums[left][0] + tmp_nums[right][0]- 若和偏大，右边元素太大，右指针左移有机会减小总和
- 若和偏小，左边元素太小，左指针右移有机会增大总和
这就是双指针能成立的基础。
复杂度分析
- 时间复杂度：
O(n log n)，主要消耗在排序上 - 空间复杂度：
O(n)，因为额外创建了一个保存“数值 + 原下标”的数组
这种写法的关键点
1. 排序后原下标会丢失
所以必须提前记录每个元素在原数组中的位置。
2. 双指针必须建立在有序数组上
原数组无序时，不能直接左右夹击，否则移动指针没有依据。
解法二：哈希表
上面那种写法适合拿来练“排序 + 双指针”的套路。 但如果要追求更优时间复杂度，这题最经典的答案还是：哈希表一次遍历。
核心思路是这样的：
- 遍历数组中的每个数
i - 先看看它是不是之前某个数正在等的“补数”
- 如果是，直接返回答案
- 如果不是，就把
target - i记进哈希表里，表示“我在等这个数出现”
代码实现
class Solution(object): def twoSum(self, nums, target): """ :type nums: List[int] :type target: int :rtype: List[int] """ hashtable = dict() for idx, i in enumerate(nums): if i in hashtable: return [hashtable[i], idx] hashtable[target - i] = idx return [-1, -1]思路解析
这个写法很妙，妙在它不是把“已经出现过的值”塞进去， 而是把未来希望遇到的补数塞进去。
比如：
nums = [2, 7, 11, 15]target = 9遍历过程如下：
第一步：遍历到 2
- 当前值是
2 - 它不在哈希表里
- 说明之前没人等它
- 那就把
target - 2 = 7记进去
此时哈希表为：
{7: 0}意思就是：
“我现在记住了，下次如果看到 7，就能和下标 0 的 2 凑成答案。”
第二步：遍历到 7
- 当前值是
7 - 发现
7已经在哈希表里 - 说明之前的
2正在等它
于是直接返回：
[0, 1]一遍结束，干净利索，不绕弯子。
复杂度分析
- 时间复杂度：
O(n) - 空间复杂度：
O(n)
为什么哈希表更常见
因为它快。
排序 + 双指针的做法，本质上是先把路修平再开车； 哈希表则更像看见目标就直接踩油门。
如果只是为了通过这道题，哈希表通常是更推荐的标准答案。
两种解法对比
| 解法 | 时间复杂度 | 空间复杂度 | 特点 |
|---|---|---|---|
| 排序 + 双指针 | O(n log n) | O(n) | 适合练习有序数组上的双指针思想 |
| 哈希表 | O(n) | O(n) | 更经典、更高效、面试中更常见 |
小结
这道题不难，但很适合拿来建立题感。
- 想练套路，可以写 排序 + 双指针
- 想要高效，可以写 哈希表一次遍历
如果只记一句话，那就是：
双指针靠有序，哈希表靠补数。
Hot 100 第一题，先把手感找回来。 后面继续刷，别怂，题海虽深，慢慢捞也能捞出虾味人生。🦐