Python实现哈希表求两数之和，怎么操作来着？

给学过 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 [] 你可以把它翻译成人话： d = {}：准备一个字典，记录数字和它出现的位置 for i, x in enumerate(nums)：遍历数组，同时拿到下标和值 if target - x in d：看我要找的配对数字之前有没有出现过 return [d[target - x], i]：如果出现过，直接返回两个下标 d[x] = i：如果没出现，就把当前数字存进去 十二、你现在最容易卡住的几个点 1. “哈希表”听起来陌生，其实就是 dict 在 Python 里，做这题时： 哈希表 = 字典 dict 所以别把“哈希表”想得太吓人。 你平时写的： d = {} d[5] = 10 本质上就是在用哈希表。 2. enumerate(nums) 不用怕 它就是“遍历列表时，同时拿到下标和值”。 for i, x in enumerate(nums): 等价理解为： for 下标, 元素 in nums: 当然严格来说不是这么写，但你脑子里可以这么翻译。 3. in hashtable 检查的是“键”在不在 比如： d = {2: 0, 7: 1} print(2 in d) # True print(0 in d) # False 这里检查的是键，不是值。 所以： if target - x in hashtable: 检查的是“这个数字有没有作为键存进去”。 十三、完整可运行代码 最后放一份完整版本： 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 [] nums = [2, 7, 11, 15] target = 9 print(twoSum(nums, target)) 输出结果： [0, 1] 十四、写给现在的你 如果你是“大一学过 Python 程序设计，但现在有点忘了”的状态，其实很正常。 很多人不是不会，而是： 语法有点生 代码一长就容易慌 听到“哈希表”“时间复杂度”就觉得自己不行 但这题真正核心的东西没有那么多： 知道字典 dict 可以快速查找 知道 enumerate 是同时拿下标和值 知道这题要找的是 target - 当前数 知道顺序要先查再存 把这四点想明白，这题就通了。 你现在不需要追求“一看就会自己秒写”， 只需要做到： 能读懂代码 能跟着例子模拟执行 过一会儿自己再默写一遍 这就已经是在进步了。 十五、小结 “两数之和”这道题的关键，不是在于代码有多复杂，而是在于你有没有把问题转化成： 当前数的配对值有没有在前面出现过？ 而 Python 里的字典 dict，正好可以帮我们快速完成这件事。 所以最终我们用哈希表，把原本较慢的双重循环，优化成了只遍历一次数组的写法。 最经典的实现就是： 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 [] 这不仅是一道题的解法，其实也是很多算法题里很常见的思路： 一边遍历，一边记录，一边查找。