LeetCode 热题 100 题解（1）：哈希

从今天起我们开始以 python 语言为例从入门开始解析 LeetCode 热题 100 题单LeetCode 热题 100 - 学习计划 - 力扣LeetCode全球极客挚爱的技术成长平台。第一个板块是哈希。一、什么是哈希表Hash Table哈希表是一种高效的键值对存储结构它利用哈希函数将任意类型的键转换为数组索引从而实现平均 O(1) 时间复杂度的查找、插入和删除操作。这一快速访问的核心机制在于通过哈希函数计算键对应的哈希值再将其映射到数组的特定位置。对比一般的只能用数字下标查找的数组哈希表可以用字符串、数字、元组等任意可哈希不可变类型作为查找标识。值得一提的是不可变类型指的是数据一旦创建就不能原地修改想要改只能新建一份新对象的数据而可变类型的数据可以直接修改内存中的内容无需更换存储地址。# 列表可变原地修改地址不变 lst [5] print(id(lst)) lst[0] 3 print(id(lst)) # 地址完全一样修改的是同一个列表内部内容 # 数字不可变只能更换指向地址必变 a 5 print(id(a)) a 3 print(id(a)) # 地址更换换了一个全新数字对象结果此处对于哈希表的底层原理不做过多介绍重点探讨哈希在题目中的具体应用。python 中有两大常用哈希容器字典 dict 和集合 set。1.字典 dict字典的存储形式是 {key,value}是典型的键值对映射一一对应关系。其中key 必须是不可变可哈希类型数字、字符串、元组列表和字典不能作为 key。value 则无类型限制任意数据都能存放。这种结构常用于映射存储和分组归类等场景。2.集合 set集合的存储格式为{元素1,元素2,...}仅存储元素值不包含键值对。集合具有自动去重特性且只允许存储不可变类型的元素不支持通过下标获取元素。使用 x in set 进行成员检测时平均时间复杂度为O(1)。典型应用场景包括数据去重和快速判断元素是否存在。二、例题1.两数之和解法1暴力法这是一道经典的哈希入门题。第一眼读题容易想到暴力两层循环遍历外层遍历第一个数 nums[i]内层遍历它之后所有数 nums[j]判断 nums[i] nums[j] target满足直接返回 [i,j]。class Solution(object): def twoSum(self, nums, target): n len(nums) for i in range(n): for j in range(i1, n): if nums[i] nums[j] target: return [i, j] return []这种算法的时间复杂度是 O(n^2)空间复杂度 O(1)显然数据量大时会有超时问题。所以我们考虑用哈希字典对运行时间进行优化。解法2字典问题本质是根据目标值 target 找补值如果把遍历过的数字以数值:下标的键值对形式存到字典中只要补数已经遍历过我们就能直接取出对应下标实现时间复杂度 O(1) 的查询。顺着这个思路我们规划算法步骤初始化空字典 hash_map循环遍历数组同步拿到当前值 value 和下标 idx计算补数 need target - value判断补数是否存在于字典存在直接返回 [ hash_map[need], idx]不存在把当前 value:idx 存入字典继续循环。class Solution(object): def twoSum(self, nums, target): :type nums: List[int] :type target: int :rtype: List[int] hash_map {} for idx, val in enumerate(nums): need target - val if need in hash_map: self [hash_map[need], idx] hash_map[val] idx return self注意题目要求不重复使用同一个元素因此要先查补数再存入当前数字这样字典里永远只保存当前下标之前的元素不会取到自身。如此时间复杂度 O(n)数组仅遍历 1 次字典查询为常数时间空间复杂度 O(n)最坏情况字典存储全部数组元素。这体现了哈希空间换时间的核心思想。2.字母异位词分组此题可以帮助我们理解哈希字典的分组归类功能任务本质是给每一类异位词生成唯一标识 key之后我们将 key 相同的字符串存入同一个 value 列表最终取出所有分组。如何生成唯一的 key 呢注意到每组词语的字母类别及对应数量相同区别是顺序不同。因此我们可以考虑给字母重新排序得到统一的 key或是利用数组统计每个字母的数量将数组作为每组的 key。解法 1字符排序生成 key互为异位词的字符串字符排序后得到的字符序列完全一致。注意前文提到过list 不可哈希需转为元组tuple作为字典 key。class Solution1(object): def groupAnagrams(self, strs): :type strs: List[str] :rtype: List[List[str]] dic {} for s in strs: key tuple(sorted(s)) if key not in dic: dic[key] [] dic[key].append(s) return list(dic.values())这种写法时间复杂度是 O(nklog k)n 为字符串总数k 为单字符串最大长度排序耗时 klog k空间复杂度是 O(nk)存储全部字符串与哈希键。由于长字符串排序存在一定的性能损耗所以我们考虑用字母计数法优化。解法 2字母计数生成 key小写字母仅 26 个我们统计每个字符串中 a-z 出现次数用长度 26 的计数元组作为 key。由于异位词的字母频率分布完全相同无需进行排序操作这样就能避免 klog k 的时间复杂度开销。class Solution2(object): def groupAnagrams(self, strs): :type strs: List[str] :rtype: List[List[str]] dic {} for s in strs: cnt [0]*26 for c in s: idx ord(c) - ord(a) cnt[idx]1 key tuple(cnt) if key not in dic: dic[key] [] dic[key].append(s) return list(dic.values())这种算法仅遍历每个字符串的全部字符消除了排序时间复杂度降到 O(nk)。本题中我们用到了排序映射、特征计数映射方法这些都是字符串哈希分组通用模板。3.最长连续序列题目给的 nums 数组具有无序性、重复性暴力遍历会大量重复计算而如果对数组进行排序再统计时间复杂度将达到 O(nlog n)不符合题目要求。这时候我们就可以使用set 哈希集合对数组去重同时实现平均 O(1) 的查询。考虑好数据结构后算法思想其实很简单我们仅从连续段起点开始统计长度如果 x-1 不在集合中说明 x 是一段连续数字的开头最短长度为 1即 x 本身从起点向后循环查找 x1、x2……再统计当前段长度更新全局最大值。class Solution(object): def longestConsecutive(self, nums): num_set set(nums) max_len 0 for x in num_set: if x - 1 not in num_set: cur, length x, 1 while cur 1 in num_set: cur 1 length 1 max_len max(max_len, length) return max_len这种算法的时间复杂度是 O(n)每个元素仅参与一次内层循环查询哈希查询是常数时间。空间复杂度是 O(n)哈希集合存储全部去重数字。通过本题我们了解了哈希容器 set 的核心用途去重和O (1) 快速判存。三、总结经过三道基础例题训练我们对于哈希表、可哈希类型、哈希容器有了更深的理解。哈希表基于哈希函数映射将原本列表遍历查找的 O(n) 时间复杂度压缩至平均 O(1)。其本质就是额外开辟内存存储映射 / 元素用存储空间换取查询效率。在处理类似数组或字符串相关问题时我们首先需要明确需求若需保存关联关系实现反向查找如值-下标、特征-分组则使用字典dict若只需去重或判断元素是否存在则使用集合set。构造哈希键时若需要分组操作可将同类数据的共同特征作为键。关于哈希表的底层细节和更多进阶例题读者们可以自行进一步拓展延申。