Python实现哈希表求两数之和，怎么操作来着？
摘要：给学过 Python 程序设计，但现在有点忘了的同学，尽量讲得慢一点、顺一点，不装懂，也不跳步。 一、先说这道题在问什么 “两数之和”是 LeetCode 里非常经典的一道入门题。 题目大意是： 给你一个整数数组 nums 和一个目标值 t
给学过 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，并且同时拿到下标和元素值。