当前位置：首页 > news >正文

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

news 2026/7/21 0:36:32

从今天起，我们开始以 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(i+1, 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 本身），从起点向后循环查找 x+1、x+2……，再统计当前段长度，更新全局最大值。

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) 快速判存。