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 []