【LC 1】两数之和：「先查再存」的顺序一反过来，就会匹配到自己
适用读者：刚开始刷题、或者一直觉得"这题不就是两重循环吗"的人
技术栈：Python 为主，附 Java 版
难度：简单 —— 但它是哈希表思路的入门课，而且藏着两句不能颠倒的代码
收获：一次遍历 + 哈希表为什么是 O(n)、if need in seen 和 seen[x] = i 为什么不能换序，以及 LC 167 / 15 / 18 / 454 一整串"n 数之和"的演化路线
题目
给定一个整数数组
nums 和一个整数目标值
target，请你在该数组中找出
和为目标值的那两个整数，并返回它们的数组下标。
你可以假设
每种输入只会对应一个答案，但是，数组中
同一个元素在答案里不能重复出现。
输入：nums = [2, 7, 11, 15], target = 9
输出：[0, 1]
解释：因为 nums[0] + nums[1] == 9，返回 [0, 1]。
输入：nums = [3, 2, 4], target = 6
输出：[1, 2]
输入：nums = [3, 3], target = 6
输出：[0, 1]
这题是绝大多数人的
第一道 LeetCode。它短、好懂、样例一眼就能算出来 —— 但也正因为如此，很多人用两重循环写完就翻篇了，没注意到它其实在教三件更重要的事：
一、先说清楚这题在考什么
1.1 暴力：两重循环
最直白的写法，选一个
i，再往后一个个试
j：
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
n = len(nums)
for i in range(n):
for j in range(i + 1, n):
if nums[i] + nums[j] == target:
return [i, j]
return []
。n = 10⁴ 时是 10⁸ 次运算，勉强能过；但这题的定位是"诱导你想到更快的方法"。
注意
for j in range(i + 1, n) 里的
i + 1 —— 这个
+1 就是"同一个元素不能重复使用"在暴力写法里的体现（只往后看，不看自己）。
1.2 换个问法：站在 i 的位置，问"我缺的那个数之前来过吗"
把思路反过来：
不要问"i 和 j 加起来是不是 target"，
而是问"我需要的那个数 target - nums[i]，在我左边出现过吗？"
这么一问，问题就从"两两组合"变成了"
查找一个值在不在"—— 而"查一个值在不在"有 O(1) 的做法：
哈希表。
于是只需要一次遍历：
i = 0: x = 2，我需要 9 - 2 = 7。我左边有什么？什么都没有。→ 把 2 记下来
i = 1: x = 7，我需要 9 - 7 = 2。我左边有什么？有 2（下标 0）！→ 命中，返回 [0, 1]
一遍扫完。
1.3 哈希表里存什么
所以表是
{值: 下标}。这也是为什么这题不能用
set：
set 只能回答"在不在"，回答不了"在哪"。
二、完整代码
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
seen = {} # 值 -> 它的下标
for i, x in enumerate(nums):
need = target - x
if need in seen: # ① 先在我左边找
return [seen[need], i]
seen[x] = i # ② 再把自己记进去
return []
，但每一句都有讲究：
表里装的是"
已经见过的元素"。
注意它一开始是空的 —— 空表意味着
i = 0 时什么也查不到，这很重要。
我要的那个数。
不要在这里纠结"
i 和
j 谁大谁小"—— 因为查表天然只会查到左边的元素。
if need in seen:
return [seen[need], i]
命中就返回。注意返回顺序：
seen[need] 一定在
i 左边，所以
[seen[need], i] 天然是升序的。
再存。 这两句的先后顺序就是本文的全部重点。
三、动画：看着表一步步长起来
下面这个动画把上面 6 帧推演过程逐帧画出来。图里：
- 一排格子是
nums；当前正在处理的元素橙色高亮，已经登记进表的淡绿底，答案的两个元素金色 + 外环；
- 上方
i= 指针指向当前元素；
- 下方
seen 卡片表显示 值 → 下标：刚存进去的绿色、被查中的金色；
- 答案连线把命中的两个格子连起来；
- 底部横幅实时显示"我需要
target - x 等于几、查表结果如何"。
看的时候重点盯三处：
- 第 2 帧（
i = 0）：算出来"我需要 7"，然后查表 —— 表是空的。为什么会空？因为 i = 0 是你遇到的第一个元素，左边没有任何东西。这一帧的存在本身就说明了"查表只能查到左边"；
- 第 3 帧：把
2 → 0 登记进表。这一步发生在查表之后；
- 第 4 帧（
i = 1）：需要 9 - 7 = 2，一查 —— 表里下标 0 就是它。于是返回 [0, 1]。
第 3 帧和第 4 帧之间，就是"先查再存"这五个字的全部含义。
四、完整推演表（6 帧逐帧）
下表是动画每一帧的真实数据（
nums = [2, 7, 11, 15]，
target = 9）：
两个值得对照看的点：
第 1 帧和第 2 帧是分开的两件事。 "查表"和"登记"是两个动作，动画把它们拆成两帧就是为了让你看清
先后顺序：
第 1 帧：查表 → 表里是 {} ← 此刻还没有 2
第 2 帧：登记 → 表里变成 {2: 0} ← 2 是在"查完之后"才进去的
如果顺序反过来，第 1 帧就会变成"表里已经有
{2: 0} 了"，然后拿
need = 7 去查…… 嗯，这个例子里查不到 7，所以看起来没问题。
这正是这题最阴的地方 —— 见下一节。
第 3 帧之后就没有第 4 轮了。 因为
i = 2（值 11）已经用不着查了 —— 题目保证"只有一个答案"，找到就能立刻返回。
五、本题唯一真正的难点：「先查再存」，顺序不能反
把两句调换一下，代码看起来同样"合理"：
for i, x in enumerate(nums):
seen[x] = i # ❌ 先存
need = target - x
if need in seen:
return [seen[need], i]
它错在哪？
当 target == 2 * x 时，
need = target - x = x —— 你要找的就是你自己。而"先存"意味着
自己已经被放进表里了，于是一查就中，返回的
seen[need] 就是
i：
5.1 [3, 3] 配 target = 6：逐帧对照
错误写法在两个下标相同时，
答案本身就是非法的 —— 它违反的是题目那句"同一个元素在答案里不能重复出现"，而不是"算错了和"。
5.2 触发条件：target == 2 * x
这个 bug 不是"偶尔错"，它有
精确的触发条件：
当前元素恰好是目标值的一半。
用这个条件去检查两组官方样例，会看到一个很有意思的结果：
看到问题了吗：官方给的
第一组样例（
[2, 7, 11, 15] 配
9）是
唯一一组不触发这个 bug 的 —— 因为 9 的一半不是整数，数组里不存在"目标值的一半"。
于是一个很危险的情况出现了：
用错误写法跑第一组样例，得到正确答案 [0, 1]，你会以为自己写对了。
这和"写完就过样例"的刷题习惯直接冲突。
结论：这题不能靠上面那组官方样例来验证，必须自己构造 target = 2 * x 的用例。
5.3 一句话记住
先问"前面有我缺的那个数吗"，再把自己登记进去。
if need in seen: # ① 先查 —— 此刻表里只有左边的东西
return [seen[need], i]
seen[x] = i # ② 再存
5.4 为什么"先查再存"就自动满足了"不重复使用同一元素"
这是这题最值得想明白的一层。
题目要求"同一个元素不能在答案里出现两次"。在暴力写法里，靠的是
for j in range(i + 1, n) 这个
+1；而在哈希表写法里，
它是被"先查再存"自动保证的：
查表发生的那一刻，seen 里装的只有 nums[0..i-1] —— 也就是"当前元素左边的所有东西"。
所以任何命中的下标必然 < i，不可能是自己。
换句话说：
"先查再存"这个顺序，同时干了两件事 ——
- 让查找变成 O(1)（这是哈希表本身的功劳）；
- 让"不重复用同一元素"这条约束不需要额外判断就成立（这是顺序的功劳）。
如果改成"先存再查"，第 2 点就没了，你就必须像下面这种写法一样额外加一句
!= i 判断。
六、另一种写法：先建完整张表，再查
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
seen = {}
for i, x in enumerate(nums): # 第一遍：把整张表建好
seen[x] = i
for i, x in enumerate(nums): # 第二遍：再查
need = target - x
if need in seen and seen[need] != i: # ← 必须排除自己
return [i, seen[need]]
return []
，但代价是：
- 要扫两遍（虽然还是 O(n)，但常数翻倍）；
- 必须显式写
seen[need] != i —— 也就是把"不重复用同一元素"变成一个需要人肉维护的判断，而不是让它自动成立；
- 表里存的是"最后一个下标"，重复值会互相覆盖。比如
[3, 3, 3] 配 target = 6，表里只剩 {3: 2}，返回 [0, 2] —— 依然对，但如果题目要求的是"所有答案对"，这种覆盖就会漏解。
所以推荐第一种（先查再存）：一遍扫完、约束自动满足、重复值也不怕（表里还没被后来的覆盖就命中了）。
一句话对比：
先查再存 = 边走边问（表只装左边的，天然不会问到自己）；
先建再查 = 先拍照再核对（表装了全部，必须自己排除自己）。
七、变体一：LC 167 有序数组 → 换双指针，省掉整张表
LC 167 两数之和 II — 输入有序数组：数组
已经是升序的，要求返回下标（题目叫"下标从 1 开始"，所以要
+1）。
既然有序，哈希表就
不必要了 —— 用
双指针，空间从 O(n) 降到
O(1)：
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
left, right = 0, len(numbers) - 1
while left < right:
s = numbers[left] + numbers[right]
if s == target:
return [left + 1, right + 1] # 题目要求 1-based
if s < target:
left += 1 # 和太小 → 左指针右移（换更大的数）
else:
right -= 1 # 和太大 → 右指针左移（换更小的数）
return []
因为数组有序，
left 往右走会让和
变大，
right 往左走会让和
变小 —— 两个方向都是
单调的。所以可以"根据当前和偏大还是偏小，确定性地移动某一侧"，一步都不浪费。
7.1 两题逐项对照
这张表本身就是一道面试题：题目从"无序"变成"有序"，信息量增加了，所以可以用更省的办法。
有序这个前提不是白给的，它是可以被利用的。
7.2 和 LC 3 滑动窗口是同一个思想
上一篇文章讲的 LC 3（滑动窗口）用的是完全一样的心法：
利用单调性，让指针只往一个方向走，永远不回头。
- LC 3 里：
left 只往右，因为"窗口左边的字符已经被排除了，回头就会引入重复"；
- LC 167 里：
left 只往右、right 只往左，因为"和只会单调变化"。
"指针能不能只往一个方向走"是这两个算法的共同根基。 想清楚这一点，这两族题就串起来了。
八、变体二：n 数之和的演化路线
LC 1 是"两数之和"。把"两数"推广出去，就长出了一整条题链：
演化逻辑只有一条：
固定的数增加一个 → 复杂度多一维；剩下的"两数"始终用 O(n) 的 LC 1 或 LC 167 收尾。
以 LC 15 三数之和为例：
def threeSum(nums):
nums.sort()
res = []
for i in range(len(nums) - 2):
if i > 0 and nums[i] == nums[i - 1]: # 跳过重复的固定数
continue
left, right = i + 1, len(nums) - 1
while left < right: # ← 这里就是 LC 167
s = nums[i] + nums[left] + nums[right]
if s == 0:
res.append([nums[i], nums[left], nums[right]])
while left < right and nums[left] == nums[left + 1]:
left += 1 # 跳过重复
while left < right and nums[right] == nums[right - 1]:
right -= 1
left += 1
right -= 1
elif s < 0:
left += 1
else:
right -= 1
return res
：① 让双指针能用（有序才单调）；② 让"跳过重复答案"变得容易（相同的数挨在一起）。所以 LC 15 用的是
"排序 + 双指针"而不是哈希 —— 因为要
去重，哈希反而麻烦。
这就是"为什么 LC 1 用哈希、LC 15 用双指针"的答案：
九、Java 版
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> seen = new HashMap<>(); // 值 -> 下标
for (int i = 0; i < nums.length; i++) {
int need = target - nums[i];
if (seen.containsKey(need)) { // ① 先查
return new int[] { seen.get(need), i };
}
seen.put(nums[i], i); // ② 再存
}
return new int[] {};
}
}
：
- 必须用
Map<Integer, Integer>，不能用 Set<Integer> —— 题目要返回下标，Set 只回答"在不在"。
containsKey 而不是 get(...) != null —— 虽然 Integer 可以是 null，但 containsKey 语义更清楚，也避免了"值为 0 时被误判"的隐患。new int[] {} 而不是 null —— LeetCode 上返回 null 也行，但空数组更安全（调用方不用判空）。
如果只在 ASCII 范围内、并且可以接受数组下标化，也可以用数组代替哈希（本题不适用，因为值可能是大数或负数）。
十、边界情况与常见坑
边界情况
常见坑
坑 1：先存再查（§5）⚠️ 最隐蔽
触发条件是
target == 2 * x。
官方第一组样例恰好不触发，会让你误以为写对了。
坑 2：用 set 而不是字典
seen = set() # ❌ 只能回答"在不在"，拿不到下标
题目要返回
下标，必须存
值 → 下标。
坑 3：把"值"当假值判断
if seen.get(need): # ❌ 当 need == 0、而 seen[0] == 0 时，
# 取到 0 是假值，判断会失败
if need in seen: # ✅
if seen.get(need) is not None: # ✅ 也可以
[0, 0] 配
target = 0 就会踩这个坑。
坑 4：返回顺序反了
return [i, seen[need]] # 下标可能是降序的
seen[need] 一定在
i 左边，所以返回
[seen[need], i] 才是升序。虽然 LeetCode 对顺序宽容，但
面试时返回降序会被追问。
坑 5：忘记"只有一个答案"这个前提
题目保证唯一解，所以可以
命中就 return。如果要找
所有答案对：
- 不能提前
return；
-
seen 得存"值 →
下标列表"（不能只存一个下标，否则重复值会漏解）。
坑 6：target - x 溢出（其他语言）
Java / C++ 里
target - x 可能溢出
int。本题数据范围安全，但如果边界接近
Integer.MIN_VALUE，要开
long。
十一、面试怎么答
第一步：先给结论和复杂度
"一次遍历加一个哈希表。表里存'值 → 下标'；每走到一个元素，先算 target - x，看看它在不在表里，在就返回，不在就把自己存进去。时间 O(n)，空间 O(n)。"
第二步：主动说清"为什么是 O(n)"
"暴力是 O(n²)，因为它在枚举组合。换成哈希之后，问题从'两两组合'变成了'查一个值在不在'，而这一步是 O(1)，所以整体降成 O(n)。"
第三步：主动说清两句话的顺序（这是最关键的一句）
"关键是先查再存。查表的时候表里只有当前元素左边的，所以任何命中下标都 < i，不可能是自己 —— '同一元素不能重复使用'这条约束就自动满足了，不需要额外判断。"
第四步：主动给反例
"如果反过来先存再查，当 target == 2 * x 时就会查到自己，返回 [i, i]。比如 [3, 3] 配 target = 6，错误写法返回 [0, 0]。而且注意：官方给的第一组样例 [2,7,11,15] 配 9 恰好不会触发（9 的一半不是整数），所以这个 bug 靠跑那个样例是发现不了的。"
如果被追问"数组有序呢"：
"有序的话哈希就不必要了，可以双指针：和偏小就左指针右移、偏大就右指针左移，因为有序保证了单调性。空间从 O(n) 降到 O(1)。这就是 LC 167。"
如果被追问"三数之和还能用哈希吗"：
"能用但不好用 —— 因为三数之和要求答案去重，而哈希很难处理'同一组解被不同下标重复找到'的问题。所以 LC 15 走的是排序 + 双指针：排序既让双指针能用，又让相同的数挨在一起、方便跳过重复。"
如果被追问"要找所有答案对怎么办"：
"那就不能命中即返回，要把整表跑完；而且 seen 得存'值 → 下标列表'，不能只存一个下标，否则重复值会漏解。"
结语
LC 1 是很多人的第一道题，也是很多人"写了十几行就再也没回头看"的题。但它真正教的东西只有两点：
① 把"枚举组合"换成"查表" —— 这就是哈希表的全部意义。
② 顺序不能颠倒：先查自己缺什么，再把自己登记进去。
第二点尤其容易被忽略，因为
官方给的第一组样例恰好把它掩盖了：
[2, 7, 11, 15] target = 9 ← 9 的一半不是整数，永远不会"自匹配"
用错误写法跑这一组，你会拿到正确答案
[0, 1]，然后心满意足地提交。
所以下次写这题时，不妨顺手加一句自测：
assert twoSum([3, 3], 6) == [0, 1] # 而不是 [0, 0]
系列导航：本文是「暑期面经汇总」算法系列的第 15 篇。前作：LC 206 反转链表 · LC 21 合并两个有序链表 · LC 23 合并 K 个升序链表 · LC 141/142 环形链表 · LC 19 删除链表倒数第 N 个节点 · LC 143 重排链表 · LC 234 回文链表 · LC 160 相交链表 · LC 82 删除排序链表中的重复元素 II · LC 102 二叉树的层序遍历 · LC 236 二叉树的最近公共祖先 · LC 124 二叉树中的最大路径和 · LC 104/226 二叉树的最大深度 & 翻转二叉树 · LC 3 无重复字符的最长子串。