「LeetCode Hot 100 」哈希篇

0. 前言

LeetCode Hot 100 几乎是每位冲刺互联网大厂的同学都会接触到的经典题单,其重要性不言而喻。

本系列主要记录我的刷题过程,包括解题思路、代码实现以及学习中的思考与总结。

既是写给自己复习的笔记,也希望能给同样在刷题的你提供一些参考。

本期的主题是「哈希」,题目如下:

  1. 1. 两数之和(简单)
  2. 49. 字母异位词分组(中等)
  3. 128. 最长连续序列(中等)

1. 两数之和

1. 题目描述

image.png

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,记录已经遍历过的元素及其下标。

遍历列表时:

  1. 获取当前元素 current,计算 want = target - current。
  2. 判断 want 是否已经存在于 seen 中。
  3. 如果存在,直接返回两个元素的下标。
  4. 如果不存在,将当前元素及其下标存入字典,继续遍历。

这里还有一个细节:必须先查找,再存入当前元素。

因为题目不允许重复使用同一个位置的元素。如果先存入再查找,就可能让当前元素与自己配对。

至此,我们就通过一次遍历和字典查找,完成了「两数之和」的求解。

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. 题目描述

image.png

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. 题目描述

image.png

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. 快速查找: 判断某个元素是否存在,并获取与它关联的信息。
  2. 分组归类: 根据某种共同特征,把多个元素组织到一起。

1. 三道题中,哈希结构分别承担什么角色?

题目数据结构承担的角色
两数之和dict记录已遍历元素,快速查找下标
字母异位词分组dict根据共同特征,将字符串归入对应分组
最长连续序列set去重、快速判断数字是否存在

虽然解决的问题不同,但三道题都利用了哈希结构的快速查找能力,减少不必要的重复遍历。

2. 什么时候选择字典,什么时候选择集合?

这里有一个值得注意的区别:前两道题使用的是字典 dict,第三道题使用的是集合 set。

它们都基于哈希机制,但保存的数据不同。

  • dict: 当我们不仅需要判断元素是否存在,还需要获取或维护它关联的信息时,可以优先考虑字典。

  • set: 当我们只需要判断元素是否存在,或者需要对元素去重时,可以优先考虑集合。

当然,这并不是绝对的选择规则,具体还是需要结合题目需求。

3. 最值得记住的是什么?

回顾这三道题,我们会发现一个共同的问题:

如何避免为了寻找某个元素,而反复遍历大量数据?

这正是哈希结构能够帮助我们解决的问题。

因此,以后遇到新的算法题时,不妨先思考:

这道题是否存在大量重复查找?能不能通过字典或集合,减少这些不必要的查找操作?

比起单纯记住三道题的代码,我觉得理解这一点更有价值。

▼
text
复制代码
> - 平台同名:花萍雨呀,将硬核的知识通俗化,更多有趣的专栏待你解锁~ > - 如果这篇文章对你有用,记得一键三连再走哦! > - 我们下期见!
0个评论
点击登录,快来和大家讨论吧~
表情
图片
暂无评论
下载 APP