「LeetCode Hot 100 」哈希篇
0. 前言
LeetCode Hot 100 几乎是每位冲刺互联网大厂的同学都会接触到的经典题单,其重要性不言而喻。
本系列主要记录我的刷题过程,包括解题思路、代码实现以及学习中的思考与总结。
既是写给自己复习的笔记,也希望能给同样在刷题的你提供一些参考。
本期的主题是「哈希」,题目如下:
- 1. 两数之和(简单)
- 49. 字母异位词分组(中等)
- 128. 最长连续序列(中等)
1. 两数之和
1. 题目描述

2. 解题思路
上来就是经典中的经典——两数之和,堪比第一个英语单词是 abandon。
这道题有两个值得注意的限制条件:
-
只有一个有效答案: 不需要考虑多组答案的情况。
-
不能重复使用同一个元素: 即使某个数字的两倍等于
target,也不能重复使用同一个下标。
最开始萍雨就忽略了第一个条件,还考虑过下面这种情况:
▼text复制代码nums = [1, 3, 2, 2] target = 4
这里存在两组符合条件的下标:[0, 1] 和 [2, 3]。但题目已经保证不会出现这种情况,属于是想复杂了,hh。
从最直接的思路出发:
我们的目标是找到两个相加等于 target 的元素,并返回它们的下标。
最直接的方法当然是使用双层 for 循环:固定一个元素,再逐个尝试其他元素,直到找到符合条件的两个数字。
这样确实能够解决问题,但时间复杂度达到了 O(n²)。
那么,有没有办法避免第二层循环呢?
假设当前遍历到的元素是 current,另一个需要寻找的元素是 want。
我们已经知道目标值 target,因此:
▼text复制代码want = target - current
也就是说,只需要遍历一次列表,就能依次确定 **current** ,并计算出对应的 **want** 。
但现在还有一个问题:
我们知道要寻找哪个数字,却不知道它是否存在,以及它对应的下标。
如果继续遍历列表寻找,依然无法避免重复查找。
这时候就可以引入字典 dict,利用它平均 O(1) 的查找能力。
我们需要建立的映射关系是:
-
Key: 元素值。
-
Value: 元素对应的下标。
这样一来,只要知道 want,就能快速判断它是否已经出现过,并获取对应的下标。
至于为什么这样设计 Key 和 Value,我专门整理了一篇文章:《Python 字典:Key 和 Value 到底应该如何设计?》,感兴趣的小伙伴可以跳转阅读。
https://juejin.cn/post/7708601192239218722
来确定一下最终的思路:
使用一个字典 seen,记录已经遍历过的元素及其下标。
遍历列表时:
- 获取当前元素
current,计算want = target - current。 - 判断
want是否已经存在于seen中。 - 如果存在,直接返回两个元素的下标。
- 如果不存在,将当前元素及其下标存入字典,继续遍历。
这里还有一个细节:必须先查找,再存入当前元素。
因为题目不允许重复使用同一个位置的元素。如果先存入再查找,就可能让当前元素与自己配对。
至此,我们就通过一次遍历和字典查找,完成了「两数之和」的求解。
3. 代码实现
▼text复制代码# 记录已经遍历过的元素及其下标 seen = {} for i, num in enumerate(nums): want = target - num # 在已经遍历过的元素中寻找 want if want in seen: return [seen[want], i] # 先查找,再存入,避免重复使用当前元素 seen[num] = i
4. 复杂度分析
1. 时间复杂度
核心问题:随着输入规模增大,算法的计算工作量如何增长?
我们先来确定 n 代表什么,在这道题当中,n 就是 nums 列表的长度。
接着观察一下循环操作。
for 循环最多执行 n 次,而每次循环内部的计算、字典查找与插入操作,平均时间复杂度均为 O(1)。
因此整个算法的平均时间复杂度为 O(n)。
唯一需要注意的一点,就是下面的查找,Python 字典的查找平均时间复杂度是 O(1)。
但这里如果是列表的查找,那么最坏的时间复杂度是可以到 O(n) 的,这个算法的最坏的时间复杂度就会变为 O(n²)。
▼text复制代码if want in seen:
2. 空间复杂度
核心问题:随着输入规模增大,算法额外需要同时占用的存储空间如何增长?
这道题的 n 和时间复杂度一样,都是列表 nums 的长度。
一般来说,同一道题的时间复杂度和空间复杂度中的 n 是同一个含义。
接下来看一下有没有额外占用空间的部分?
是有的——字典。
那么字典最多会保存多少个键值对呢?
n - 1 个,找到答案之后就会立即返回。
对应的空间复杂度为 O(n)。
2. 字母异位词分组
1. 题目描述

2. 解题思路
这道题最核心的点是如何判断:字母异位词。
字母异位词有哪些特征呢?
排序之后的字符串是完全相同的。
如果我们把这些字符串都按照字母顺序重新排好之后,如何来判断是不是同一个呢?
字典除了两数之和当中的快速查找这个功能之外,还有一个经常使用的功能:
分组归类: 根据某种共同特征,把多个元素组织到一起。
这道题当中,我们就会用到这个功能。
前面我们提及过了,字母异位词在排序之后的字符串是完全相同的。
将多个元素组织到一起,这些元素就是原字符串。
每涉及到字典就要设计其 Key 和 Value。
我们的需求是:通过排序之后的字符串来判断,将排序之后一样的字符串组织到一起。
那么我们就是通过排序之后的字符串来查询,那么 Key 就是排序之后的字符串。
我们需要将具有相同排序结果的原始字符串组织到一起。
3. 代码实现
▼text复制代码groups = {} # sorted() 对字符串中的字符排序,返回列表 # ''.join() 将字符列表拼接为字符串 for s in strs: key = ''.join(sorted(s)) if key in groups: groups[key].append(s) else: groups[key] = [s] return list(groups.values())
4. 复杂度分析
1. 时间复杂度
核心问题:随着输入规模增大,算法的计算工作量如何增长?
在这道题当中输入的是一个字符串列表:
▼text复制代码strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
实际上会有两个不同的规模:
n:列表当中的元素个数。k:每个字符串的最大长度。
接着观察循环中的主要操作:
| 操作 | 时间复杂度 |
|---|---|
sorted(s) | O(k log k) |
''.join(...) | O(k) |
key in groups | 平均 O(k),考虑字符串 Key 的处理成本 |
groups[key].append(s) | 列表追加均摊 O(1) |
groups[key] = [s] | 字典插入平均 O(k),考虑字符串 Key 的处理成本 |
这里有一个值得注意的地方:为什么「两数之和」中的字典查找是 O(1),而这道题却可能是 O(k)?
区别主要在于 Key 的类型:
-
两数之和: Key 是整数,通常将哈希计算视为 O(1),因此字典查找平均为 O(1)。
-
字母异位词分组: Key 是字符串,计算一个长度为
k的字符串的哈希值,首次通常需要 O(k) 时间。
回到这道题,循环最多执行 n 次,每次都需要对字符串进行排序。
由于排序的 O(k log k) 是每轮主要的时间开销,因此整个算法的时间复杂度为 O(nklogk)。
2. 空间复杂度
核心问题:随着输入规模增大,算法额外需要同时占用的存储空间如何增长?
我们来看一下这个字典哈,这个字典是比较特殊的,字典当中的 Value 是列表。
▼text复制代码groups = { "aet": ["eat", "tea", "ate"], "ant": ["tan", "nat"] }
我们需要考虑两个部分:
- 字典当中的 Key:最坏是有 n 个不同的分组,每个 Key 最多 k 个字符。
- 字典当中的 Value:所有分组列表合起来保存了 n 个原始字符串的引用。
对于这个算法的时间复杂度是O(nk)。
3. 最长连续序列
1. 题目描述

2. 解题思路
要找出数字连续的最长序列,并返回该序列的长度。
不用关心这个最长序列具体是什么,只返回长度的话,难度会小一些。
有两个非常重要的限制条件。
第一个是时间复杂度必须是 O(n)。
像是上道题当中的 sorted() 排序方法就无法使用了,因为其时间复杂度是 O(log(n)),如果我没记错的话,反正我记得是带一个 log 的。
第二个是重复的数字只计算一次。
既然重复的数字没有意义,那么我们能不能通过某种数据结构来实现去重呢?
是可以的,能够实现我们目的数据结构就是 set。
在去重数据之后,我们就去思考如何找到数字连续的最长序列了。
我们来拆解一下数字连续的最长序列的组成条件会是哪些,或者需要满足哪些条件?
我们首先要找到起始点,然后需要去看这个起始点之后的 +1 的那个元素存不存在。
那么我们如何找到这个起始点呢,或者起始点的条件是什么呢?
是起始点的前一个元素不存在。
我们再引入记录连续当前和历史最长序列长度的变量就可以了。
3. 代码实现
▼text复制代码# 当前最长的连续序列长度 max_len = 0 # 去重,使用集合提高查询效率 num_set = set(nums) for num in num_set: # 如果 num - 1 不在集合中 # 说明当前数字是某段连续序列的起点 if num - 1 not in num_set: current_num = num current_len = 1 while current_num + 1 in num_set: current_len += 1 current_num += 1 # 当前序列统计结束后 # 更新最长连续序列长度 if current_len > max_len: max_len = current_len return max_len
4. 复杂度分析
1. 时间复杂度
核心问题:随着输入规模增大,算法的计算工作量如何增长?
在这道题当中 n 代表的是原始列表 nums 的长度。
创建集合需要先遍历原始列表,平均的时间复杂度是 O(n)。
接着观察循环,会发现是有两层循环的,for 循环的里面还有一个 while 循环。
这里尤其要注意,不要看到双循环就想当然的觉得是 O(n²) 哈~
我们还是要看大致的执行次数的。
外层 for 循环,最多检查 n 个不同的数字。
所有 while 循环加起来的数量级也是在 O(n) 次。
那么时间复杂度就是 O(n)。
2. 空间复杂度
核心问题:随着输入规模增大,算法额外需要同时占用的存储空间如何增长?
在这道题当中 n 代表的是去重之后的集合长度。
去重的 set 是额外占用空间的主要部分,最多会保存 n 个元素,也就是 nums 当中完全没有重复的元素
所以空间复杂度就是 O(n)。
4. 总结
到这里,LeetCode Hot 100 的哈希专题就告一段落了。
经过这三道题,我们接触到了哈希结构的两种典型用途:
- 快速查找: 判断某个元素是否存在,并获取与它关联的信息。
- 分组归类: 根据某种共同特征,把多个元素组织到一起。
1. 三道题中,哈希结构分别承担什么角色?
| 题目 | 数据结构 | 承担的角色 |
|---|---|---|
| 两数之和 | dict | 记录已遍历元素,快速查找下标 |
| 字母异位词分组 | dict | 根据共同特征,将字符串归入对应分组 |
| 最长连续序列 | set | 去重、快速判断数字是否存在 |
虽然解决的问题不同,但三道题都利用了哈希结构的快速查找能力,减少不必要的重复遍历。
2. 什么时候选择字典,什么时候选择集合?
这里有一个值得注意的区别:前两道题使用的是字典 dict,第三道题使用的是集合 set。
它们都基于哈希机制,但保存的数据不同。
-
dict: 当我们不仅需要判断元素是否存在,还需要获取或维护它关联的信息时,可以优先考虑字典。 -
set: 当我们只需要判断元素是否存在,或者需要对元素去重时,可以优先考虑集合。
当然,这并不是绝对的选择规则,具体还是需要结合题目需求。
3. 最值得记住的是什么?
回顾这三道题,我们会发现一个共同的问题:
如何避免为了寻找某个元素,而反复遍历大量数据?
这正是哈希结构能够帮助我们解决的问题。
因此,以后遇到新的算法题时,不妨先思考:
这道题是否存在大量重复查找?能不能通过字典或集合,减少这些不必要的查找操作?
比起单纯记住三道题的代码,我觉得理解这一点更有价值。
▼text复制代码> - 平台同名:花萍雨呀,将硬核的知识通俗化,更多有趣的专栏待你解锁~ > - 如果这篇文章对你有用,记得一键三连再走哦! > - 我们下期见!
