Hot100 01 | 两数之和：从暴力枚举到哈希表

如果这是你正式开始刷 LeetCode Hot100 的第一题，那这篇文章就按“真正的新手视角”来讲：不默认你会哈希表，不默认你熟悉 Python，也不默认你已经有刷题套路。

这题的题号是 1. 两数之和（Two Sum）。题目不难，但非常经典，因为它几乎把刷题时最重要的几个习惯都包含进来了：

先把题目翻译成人话
先写出最笨但正确的方法
再考虑能不能优化
最后总结这题属于什么模式

1. 题目到底在说什么

题目会给你：

一个整数数组 nums
一个目标值 target

你要做的是：

在数组里找到两个数
这两个数相加等于 target
返回这两个数的下标

注意，返回的是“下标”，不是“数字本身”。

比如题目给出：

1	nums = [2, 7, 11, 15], target = 9

因为：

2 + 7 = 9

所以返回：

[0, 1]

这里的 0 和 1 是位置，不是答案中的两个数。

2. 先把题目的限制看懂

这题还有两个很重要的条件：

你可以假设每种输入只会对应一个答案
不能重复使用同一个元素

第二句话很关键。

比如 target = 6，数组里只有一个 3，那你不能拿这个 3 自己和自己相加。

也就是说，这题找的是“两个人组队”，不是“一个人和自己凑数”。

3. 先别想优化，先想最直接的方法

第一次刷题时，最容易犯的错误是：

一上来就想最优解
一看到题解里有“哈希表”就紧张
结果连最基本的思路都没先理顺

其实正确顺序应该是：

先想最直接的方法
只要它正确，就先写出来
再问自己：有没有更快的方法

所以这题先想一个最笨的方法。

4. 方法一：暴力枚举

4.1 思路

最直接的想法就是：

先拿第 1 个数
再和后面的每个数都试一遍
看它们相加是不是 target
如果不是，就换第 2 个数继续试
一直试到找到为止

这就叫“暴力枚举”。

4.2 用例子手动模拟

例子：

1	nums = [2, 7, 11, 15], target = 9

我们这样试：

先拿 2
试 2 + 7 = 9
已经等于目标值了
所以答案就是下标 [0, 1]

如果第一个没命中，就继续试：

2 + 11
2 + 15

然后再换下一个起点。

4.3 先看 Python Tutor 版代码

在 Python Tutor 里，建议你不要直接贴 LeetCode 的 class Solution 版本，而是先写成普通函数，方便观察变量变化。

def two_sum(nums, target):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]

result = two_sum([2, 7, 11, 15], 9)
print(result)

先看第一张图。此时程序刚进入暴力法的第一轮外层循环：

这张图里你重点看三件事：

i = 0，说明现在固定的第一个数是 nums[0]
nums 还是原数组 [2, 7, 11, 15]
下一步程序要进入内层循环，开始尝试不同的 j

再看第二张图。此时已经比较到了 nums[0] + nums[1]，并且返回值已经出现：

这里你可以直接观察到：

i = 0
j = 1
返回值是 [0, 1]

这就说明程序已经找到答案，所以不会继续往后试了。

4.4 LeetCode 可提交版代码

class Solution:
    def twoSum(self, nums, target):
        for i in range(len(nums)):
            for j in range(i + 1, len(nums)):
                if nums[i] + nums[j] == target:
                    return [i, j]

4.5 每一行都在做什么

先看外层循环：

1	for i in range(len(nums)):

这句话的意思是：

len(nums) 代表数组长度
range(len(nums)) 会生成 0, 1, 2, ...
i 表示“第一个数的下标”

如果 nums = [2, 7, 11, 15]，那么：

1 2	len(nums) = 4 range(len(nums)) = 0, 1, 2, 3

所以 i 会依次取：

再看内层循环：

1	for j in range(i + 1, len(nums)):

这句话的意思是：

j 是“第二个数的下标”
它从 i + 1 开始

为什么不是从 0 开始？

因为这样可以避免两件麻烦事：

避免自己和自己比较
避免重复比较

举个例子：

当 i = 0 时，j 从 1 开始
所以会比较 (0, 1)、(0, 2)、(0, 3)
但不会比较 (0, 0)
也不会以后再重复比较 (1, 0)

接着看判断：

1	if nums[i] + nums[j] == target:

意思是：

取出位置 i 的数
再取出位置 j 的数
把它们加起来
看是否等于目标值 target

如果相等，就返回：

1	return [i, j]

这说明：

找到了正确答案
返回这两个位置
函数立刻结束

4.6 用程序运行顺序再走一遍

还是这组数据：

1	nums = [2, 7, 11, 15], target = 9

第一轮：

i = 0
j = 1
比较 nums[0] + nums[1]
也就是 2 + 7 = 9
条件成立
直接返回 [0, 1]

所以这题在第一个外层循环里就结束了。

4.7 这个方法的优缺点

优点：

好想
好写
非常适合第一次刷题时建立信心

缺点：

两层循环，效率不高

时间复杂度是：

O(n^2)

因为你基本上把数组里的数两两都试了一遍。

5. 题目为什么还要你继续想

题目最后会问一句：

1	你可以想出一个时间复杂度小于 O(n^2) 的算法吗？

这句话就是在提醒你：

暴力法能做
但不是最优

那怎么优化？

关键是换一个想问题的角度。

6. 方法二：哈希表

6.1 不要死盯着“找两个数”，换个想法

当你看到当前数字是 x 时，你真正关心的不是：

“另一个数到底是谁？”

而是：

“我还差多少才能凑成 target？”

这句话非常重要。

如果：

1 2	target = 9 当前数字 = 2

那你立刻就能知道：

我还差 7

所以问题就变成了：

之前有没有出现过 7？

如果出现过，答案就找到了。

6.2 哈希表是什么

这题里的“哈希表”，你现在可以简单理解成 Python 里的字典 dict。

seen = {}

这个字典里我们准备记录：

键：某个数字
值：这个数字出现的下标

比如：

1	seen[2] = 0

意思就是：

数字 2 出现在下标 0

6.3 Python Tutor 版代码

def two_sum(nums, target):
    seen = {}

    for i in range(len(nums)):
        need = target - nums[i]

        if need in seen:
            return [seen[need], i]

        seen[nums[i]] = i

result = two_sum([2, 7, 11, 15], 9)
print(result)

第一张图对应“哈希表刚初始化完”的状态：

这时候最值得注意的是：

seen 还是一个空字典
数组已经传进来了
程序马上要开始第一轮遍历

第二张图对应“第一次把当前数字记录进字典”：

这说明：

当前 i = 0
当前数字是 2
need = 7
因为 7 不在 seen 里，所以程序把 2: 0 存了进去

第三张图对应“第二轮发现补数已经存在”：

这时程序状态非常关键：

i = 1
当前数字是 7
need = 2
字典里已经有 2: 0
所以直接返回 [0, 1]

这就是哈希表解法的核心：不是盲目找另一个数，而是先算“我还差谁”，再去字典里查它在不在。

6.4 LeetCode 可提交版代码

class Solution:
    def twoSum(self, nums, target):
        seen = {}

        for i in range(len(nums)):
            need = target - nums[i]

            if need in seen:
                return [seen[need], i]

            seen[nums[i]] = i

6.5 每一行都在做什么

先看：

seen = {}

这句话的意思是：

创建一个空字典
准备记录“我之前见过哪些数，以及它们出现的位置”

再看循环：

1	for i in range(len(nums)):

还是从左到右遍历整个数组。

接着看这句：

1	need = target - nums[i]

这是整道题的核心。

它在做的事是：

当前数是 nums[i]
要想和它凑成 target
还差一个数字 need

例如：

1
2
3

target = 9
nums[i] = 2
need = 9 - 2 = 7

所以此时不是去乱找，而是明确地问：

我之前见过 7 吗？

这就来到下一句：

1	if need in seen:

这里的 in 表示：

检查 need 这个键是否在字典 seen 里

如果在，说明：

之前已经出现过这个补数
当前这个数和之前那个数刚好能凑成 target

于是返回：

1	return [seen[need], i]

这里：

seen[need] 是之前那个数的下标
i 是当前这个数的下标

如果没找到，就执行：

1	seen[nums[i]] = i

意思是：

当前这个数还不能立刻组成答案
但我们先把它记下来
让后面的数字来找它配对

6.6 为什么一定要“先查，再存”

这个细节很重要。

顺序是：

先检查 need 在不在 seen 里
再把当前值存进去

为什么不能反过来？

因为题目说了：

不能使用同一个元素两次

如果你先存入自己，再去查，有些情况下就可能错误地把自己和自己配对。

所以标准写法是：

先查
再存

6.7 用例子完整模拟一遍

还是：

1	nums = [2, 7, 11, 15], target = 9

一开始：

seen = {}

第 1 轮

i = 0
nums[i] = 2
need = 9 - 2 = 7

检查：

7 in seen 吗？
不在，因为此时 seen 还是空的

那就把当前值记下来：

1	seen[2] = 0

现在字典变成：

{2: 0}

第 2 轮

i = 1
nums[i] = 7
need = 9 - 7 = 2

检查：

2 in seen 吗？
在

说明：

我之前见过数字 2
它在下标 0
当前数字 7 在下标 1

所以直接返回：

[0, 1]

6.8 为什么哈希表更快

暴力法的问题在于：

当前数要和很多后面的数一个个试

哈希表法的好处在于：

当前数只需要算出自己缺谁
然后直接去字典里查

而字典查询通常很快，所以总时间复杂度降成：

O(n)

空间复杂度是：

O(n)

因为字典最多可能把数组里的很多数字都存一遍。

7. 两个方法放在一起比较

7.1 暴力法

优点：容易想到，适合第一次入门
缺点：需要两层循环，效率低

7.2 哈希表法

优点：快，是这题的经典解法
缺点：第一次见时不太容易想到“补数”这个思路

7.3 面试或题解里更推荐哪个

这题最后通常推荐哈希表法，因为它更符合这题想考察的重点。

也就是说：

暴力法是你“会做题”的证明
哈希表法是你“会优化”的证明

8. 这题里你顺手学到的 Python 语法

如果你现在 Python 也不是很熟，这题正好可以顺手记住几个高频语法。

8.1 `len(nums)`

表示数组长度。

1	len([2, 7, 11, 15])

结果是：

8.2 `range(...)`

生成一个范围，常配合 for 使用。

1 2	for i in range(4): print(i)

会依次打印：

8.3 字典 `dict`

创建空字典：

seen = {}

存值：

1	seen[2] = 0

表示数字 2 对应下标 0。

8.4 `in`

检查某个键是否在字典里：

1	if need in seen:

意思是：

看看 need 这个数之前有没有出现过

8.5 `return`

返回结果，并结束函数。

1	return [i, j]

一旦执行到这里，这个函数就结束了，后面的代码不会继续执行。

9. 这题最容易犯的错

9.1 把题目理解成返回数字，而不是返回下标

题目要的是：

[0, 1]

不是：

[2, 7]

9.2 用同一个元素两次

这题不允许拿同一个位置的元素重复使用，所以暴力法内层循环才从 i + 1 开始。

9.3 哈希表法里把顺序写反

错误风险写法：

先存当前值
再检查补数

更稳的标准写法是：

先检查补数
再存当前值

9.4 在 Python Tutor 里直接粘贴 LeetCode 模板

像下面这种：

1 2	class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]:

对 Python Tutor 来说并不友好，尤其是刚开始时容易被 List、self、类定义分散注意力。

更推荐用前面给出的普通函数版本。

10. 这题属于什么模式

这题是刷题里最经典的“哈希表入门题”。

以后如果你再看到这类题：

给你一个目标值
问你数组里有没有数能配对
或者问某个数之前有没有出现过

你就要开始警觉：

能不能一边遍历，一边用字典记录已经见过的东西？

这就是这题真正要你学会的思维模式。

11. 最终推荐你背下来的版本

如果你准备把这题作为自己的第一道模板题，我建议你最后记住下面这个版本：

class Solution:
    def twoSum(self, nums, target):
        seen = {}

        for i in range(len(nums)):
            need = target - nums[i]
            if need in seen:
                return [seen[need], i]
            seen[nums[i]] = i

你现在不用追求“看一眼就背出来”，而是至少要做到：

看懂每一行是什么意思
能自己重新敲出来
能对着例子讲清楚为什么这样写

12. 这题刷完之后，你应该带走什么

如果这是你的 Hot100 第 1 题，那么这题真正的收获不是只会了一道题，而是建立了一套很好的刷题习惯：

12.1 刷题顺序

先看懂题意
再写暴力法
再想优化
最后总结题型

12.2 这题的关键词

数组
哈希表
补数
一边遍历，一边查询

12.3 一句话复盘

这题的核心不是“找两个数”，而是“遍历当前数时，快速检查它需要的补数是否已经出现过”。

13. 给刚开始刷题的自己留一个小练习

你可以做完这篇后，自己再练 3 次：

练习 1

不看文章，自己重新写出暴力法。

练习 2

不看文章，自己重新写出哈希表法。

练习 3

用 Python Tutor 跑下面两个测试：

1 2	print(two_sum([3, 2, 4], 6)) print(two_sum([3, 3], 6))

观察：

seen 是怎么一步步变化的
need 每一轮分别是多少
为什么第二个例子不会错误地用到同一个元素两次

当你能把这三件事讲清楚，这题就真的算掌握了。

1. 题目到底在说什么

2. 先把题目的限制看懂

3. 先别想优化，先想最直接的方法

4. 方法一：暴力枚举

4.1 思路

4.2 用例子手动模拟

4.3 先看 Python Tutor 版代码

4.4 LeetCode 可提交版代码

4.5 每一行都在做什么

4.6 用程序运行顺序再走一遍

4.7 这个方法的优缺点

5. 题目为什么还要你继续想

6. 方法二：哈希表

6.1 不要死盯着“找两个数”，换个想法

6.2 哈希表是什么

6.3 Python Tutor 版代码

6.4 LeetCode 可提交版代码

6.5 每一行都在做什么

6.6 为什么一定要“先查，再存”

6.7 用例子完整模拟一遍

第 1 轮

第 2 轮

6.8 为什么哈希表更快

7. 两个方法放在一起比较

7.1 暴力法

7.2 哈希表法

7.3 面试或题解里更推荐哪个

8. 这题里你顺手学到的 Python 语法

8.1 len(nums)

8.2 range(...)

8.3 字典 dict

8.4 in

8.5 return

9. 这题最容易犯的错

9.1 把题目理解成返回数字，而不是返回下标

9.2 用同一个元素两次

9.3 哈希表法里把顺序写反

9.4 在 Python Tutor 里直接粘贴 LeetCode 模板

10. 这题属于什么模式

11. 最终推荐你背下来的版本

12. 这题刷完之后，你应该带走什么

12.1 刷题顺序

12.2 这题的关键词

12.3 一句话复盘

13. 给刚开始刷题的自己留一个小练习

练习 1

练习 2

练习 3

8.1 `len(nums)`

8.2 `range(...)`

8.3 字典 `dict`

8.4 `in`

8.5 `return`