哈希表 · Hash Map

一句话骨架：扫一遍数组，每个元素先查"另一半在不在哈希表里"，没在就把自己存进去。先查后存，永远不会自配对。

何时用

• 需要 O(1) 查询"是否见过"或"配对值在哪"
• 需要按 key 分组（字母异位词 → sort 后的字符串作 key）
• 题目要求返回索引（用 dict.value 存索引），而非值本身（值用 set 即可）

关卡 1 · 两数之和（Two Sum）

学习目标

通过这一关，你应该能从空白纸默写出 8 行解法——而不需要"背"，是从结构里推出来的。

#1两数之和简单

♥♥♥♥♥+0 XP🔥 0

0 / 14

📝 题目

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那两个整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案，并且同一个元素在数组中不能使用两次。你可以按任意顺序返回答案。

示例 1

输入nums = [2, 7, 11, 15], target = 9

输出[0, 1]

💡 nums[0] + nums[1] == 9

示例 2

输入nums = [3, 2, 4], target = 6

输出[1, 2]

示例 3

输入nums = [3, 3], target = 6

输出[0, 1]

💡 相同值时返回的是两个不同位置的索引

约束

• 2 ≤ nums.length ≤ 10⁴
• -10⁹ ≤ nums[i], target ≤ 10⁹
• 只存在一个有效答案

💡 思路：一遍遍历 + 哈希表。对每个 num，先查"target - num"是否已经见过；若见过就直接配对，否则把当前 num 记入哈希表（key=值，value=索引）。

✅ 完整解法

时间 O(n) · 空间 O(n)

先把整段解法看懂，下面的选择题是对这段代码逐行的理解检验。

 1def twoSum(nums: list[int], target: int) -> list[int]: 2    seen = {} 3    for i, num in enumerate(nums): 4        complement = target - num 5        if complement in seen: 6            return [seen[complement], i] 7        seen[num] = i 8    return []

🐞 单步可视化

示例：nums = [2, 7, 11, 15], target = 9

代码L2

 1def twoSum(nums: list[int], target: int) -> list[int]: 2    seen = {} 3    for i, num in enumerate(nums): 4        complement = target - num 5        if complement in seen: 6            return [seen[complement], i] 7        seen[num] = i 8    return []

数据流

target9

nums

0

2

1

7

2

11

3

15

seen（值 → 下标）

空

1 / 9初始化哈希表 seen = {}

速度 慢中快

🧠 理解检验

每题都对应解法的某一行或某个决策

题目要求"返回索引"，那么数据结构 seen 应该是哪种最合适？

初始化 seen = ?，应当填什么？

遍历 nums 同时拿到 index 与 value，最 Pythonic 的写法是？

 1def twoSum(nums: list[int], target: int) -> list[int]: 2    seen = {} 3    for i, num in enumerate(nums): 4        complement = target - num 5        if complement in seen: 6            return [seen[complement], i] 7        seen[num] = i 8    return []

enumerate(nums) 默认从哪个索引开始？

complement 应该是 target 与 num 的什么关系？

 1def twoSum(nums: list[int], target: int) -> list[int]: 2    seen = {} 3    for i, num in enumerate(nums): 4        complement = target - num 5        if complement in seen: 6            return [seen[complement], i] 7        seen[num] = i 8    return []

检查 complement 是否已经存在于 seen 中，最快的写法是？

 1def twoSum(nums: list[int], target: int) -> list[int]: 2    seen = {} 3    for i, num in enumerate(nums): 4        complement = target - num 5        if complement in seen: 6            return [seen[complement], i] 7        seen[num] = i 8    return []

找到配对时，应当 return ?

 1def twoSum(nums: list[int], target: int) -> list[int]: 2    seen = {} 3    for i, num in enumerate(nums): 4        complement = target - num 5        if complement in seen: 6            return [seen[complement], i] 7        seen[num] = i 8    return []

seen[num] = i 这一句应当放在哪里？

 1def twoSum(nums: list[int], target: int) -> list[int]: 2    seen = {} 3    for i, num in enumerate(nums): 4        complement = target - num 5        if complement in seen: 6            return [seen[complement], i] 7        seen[num] = i 8    return []

为什么不能"先一次性把 nums 全部放入 dict，再遍历查 complement"？

该解法的时间复杂度是？

该解法的空间复杂度是？

如果题目改成"返回两个数本身（而非索引）"且数组允许排序，最优解会变成？

题目"假设每种输入只会对应一个答案，且不能重复使用同一个元素"——这句话最关键的是？

若全部循环结束都没找到，应当返回？

 1def twoSum(nums: list[int], target: int) -> list[int]: 2    seen = {} 3    for i, num in enumerate(nums): 4        complement = target - num 5        if complement in seen: 6            return [seen[complement], i] 7        seen[num] = i 8    return []

同 pattern 索引

下面的题用同一骨架就能解，时间充裕时回过头扫一遍：

题号	题名	难度	关键变形
49	字母异位词分组	中等	dict 的 key 用 ''.join(sorted(s)) 或字符计数 tuple
128	最长连续序列	中等	先 set 化，从"序列起点"（n-1 不在集合）开始向上数
41	缺失的第一个正数	困难	用数组本身做哈希（原地交换 nums[i] 到 i+1 位置）

面试常踩

1. {} 是 dict 不是 set——空集合写 set()。
2. seen[num] = i 必须在判断之后——否则可能自配对。
3. dict.keys() vs dict：用 key in d 而非 key in d.keys()，前者更地道（虽然都是 O(1)）。
4. 不要为了去重就 list(set(arr))——会丢失顺序；如要"保序去重"用 dict.fromkeys(arr)。