LeetCode-001：Python 实现哈希表求两数之和：初识哈希表
一、先说这道题在问什么
“两数之和”是 LeetCode 里非常经典的一道入门题。
题目大意是：
给你一个整数数组nums和一个目标值target，请你在数组中找到两个数，让它们相加等于target，并返回这两个数的下标。
比如：
nums = [2, 7, 11, 15] target = 9因为2 + 7 = 9，所以答案就是：
[0, 1]注意，这里返回的不是两个数本身，而是它们在数组中的位置，也就是下标。
二、最容易想到的方法：暴力枚举
如果我们刚学完 Python，最先想到的通常是：
把数组里的每两个数都试一遍，看看有没有加起来等于target的。
代码可以这样写：
def twoSum(nums, target): 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 []这段代码不难理解：
- 外层循环先固定第一个数
- 内层循环再去找第二个数
- 如果两个数相加等于目标值，就返回它们的下标
举个例子
nums = [2, 7, 11, 15] target = 9程序会这样找：
2 + 7 = 9，找到了- 返回
[0, 1]
这个方法是对的，但有个问题：慢。
因为它会把很多组合都试一遍。
如果数组很长，这种做法效率就不高了。
三、为什么它慢
假设数组里有n个元素。
暴力方法中：
- 第一个数要遍历很多次
- 对于每个第一个数，第二个数也要继续遍历
所以总的时间复杂度是：
O(n²)你可以简单理解为：
数据一多，程序要试很多很多对数字。
那有没有一种方法，让我们不用每次都重新去数组里找另一个数？
有，这就要用到哈希表。
四、什么是哈希表
很多初学者一看到“哈希表”这三个字就紧张，觉得这一定是很高级的数据结构。
其实在 Python 里，你早就接触过它了。
Python 里的哈希表，就是dict
比如：
d = {} d[2] = 0 d[7] = 1这个d本质上就是一个哈希表。
它存的是“键 -> 值”的对应关系：
- 键
2对应值0 - 键
7对应值1
在这道题里，我们可以让：
- 键：数组中的数字
- 值：这个数字对应的下标
也就是说，我们一边遍历数组，一边把“某个数出现过，而且它在什么位置”记下来。
这样以后想找某个数是否出现过，就不用重新遍历整个数组了，直接去字典里查就行。
这就是哈希表的核心作用：查找快。
五、这道题为什么适合用哈希表
题目要我们找两个数：
x + y = target如果当前我们正在看一个数x，那我们其实只需要知道：
target - x有没有在前面出现过。
例如：
target = 9 当前数 x = 7那我们就要找：
9 - 7 = 2只要之前见过2，就说明答案找到了。
所以问题就变成：
如何快速判断一个数之前有没有出现过？
这正是哈希表擅长的事。
六、核心思路：边查边存
我们可以一边遍历数组，一边做两件事：
- 先查：
target - 当前数在不在哈希表里 - 再存：把当前数和它的下标存到哈希表里
代码如下：
def twoSum(nums, target): hashtable = {} for i, x in enumerate(nums): if target - x in hashtable: return [hashtable[target - x], i] hashtable[x] = i return []这就是这道题最经典的写法。
七、先别急，这段代码一行一行看
1. 创建哈希表
hashtable = {}这里创建了一个空字典。
也可以写成：
hashtable = dict()两种写法都行。
这个字典后面会用来记录：
- 某个数字出现过没有
- 如果出现过，它的下标是多少
2. 遍历数组
for i, x in enumerate(nums):这句很多人一开始不熟，我当时也容易卡住。
它的意思是：
遍历数组nums，并且同时拿到下标和元素值。
比如：
nums = [2, 7, 11, 15]那么：
for i, x in enumerate(nums): print(i, x)输出就是：
0 2 1 7 2 11 3 15也就是说：
i是下标x是当前元素
你可以把它理解成：
for 下标, 元素 in 枚举(nums):如果你对这个写法还不熟，它其实等价于下面这种更“传统”的写法：
for i in range(len(nums)): x = nums[i]只是enumerate(nums)更方便、更常用。
3. 先查找配对数
if target - x in hashtable:这句非常关键。
假设当前的数是x，那我们要找的另一个数就是：
target - x如果这个数已经在哈希表里，说明我们之前已经见过它了。
那当前这个x和之前那个数，正好能凑成target。
4. 找到就返回答案
return [hashtable[target - x], i]这里返回的是两个下标：
hashtable[target - x]：之前那个配对数的下标i：当前数的下标
例如当前x = 7，而target = 9，那我们找的是2。
如果哈希表里有：
{2: 0}那说明数字2在下标0。
当前7在下标1。
所以返回：
[0, 1]5. 没找到就把当前数存进去
hashtable[x] = i意思是把“当前数字 -> 当前下标”这组信息存起来。
例如：
x = 2 i = 0那就相当于：
hashtable[2] = 0表示数字2出现在下标0。
八、为什么一定要“先查再存”
这个顺序不能乱。
正确写法是：
if target - x in hashtable: return [hashtable[target - x], i] hashtable[x] = i为什么不能先存再查？
因为题目要求是找两个不同位置的数。
如果你先把当前数存进去，再去查，就可能把自己和自己配对了。
举个例子：
nums = [3, 2, 4] target = 6当你遍历到第一个3时：
- 如果先存，哈希表里就有了
3 - 再查
target - 3 = 3 - 就会误以为找到了配对
但实际上，这个3只有一个，不能和自己配。
所以一定要：
- 先看前面有没有我要找的数
- 再把自己存进去
这样才能保证匹配到的是之前的元素，而不是自己。
九、完整模拟一遍执行过程
我们用这个例子来走一遍：
nums = [2, 7, 11, 15] target = 9初始状态：
hashtable = {}第 1 轮循环
当前：
i = 0 x = 2先查：
target - x = 9 - 2 = 7哈希表里有没有7？
没有，因为现在哈希表还是空的。
那就把当前数存进去：
hashtable[2] = 0此时哈希表变成：
{2: 0}第 2 轮循环
当前：
i = 1 x = 7先查：
target - x = 9 - 7 = 2哈希表里有没有2？
有，而且它对应的下标是0。
说明之前见过数字2，现在又遇到了7，它们正好相加等于9。
于是返回：
[0, 1]程序结束。
十、这段代码到底快在哪
暴力方法里，我们要反复去数组里找另一个数，查找很慢。
哈希表方法里，我们把已经出现过的数字存在字典里。
以后只需要一句：
if target - x in hashtable:就能快速判断它在不在。
因此，整个过程只需要遍历一遍数组。
时间复杂度
O(n)意思是：数组有多少个元素，就大致操作多少次。
空间复杂度
O(n)因为我们额外开了一个哈希表，最坏情况下可能要把所有元素都存进去。
十一、适合初学者记住的模板
这题你不用死记整段代码，只要记住下面这个模板就行：
def twoSum(nums, target): d = {} for i, x in enumerate(nums): if target - x in d: return [d[target - x], i] d[x] = i return []