---
title: LeetCode Hot 100 · 哈希
published: 2026-11-19
description: LeetCode Hot 100 哈希专题：数组 / set / map 三种构建方式，以及最长连续序列从暴力到 O(n) 的优化思路
tags: [LeetCode, 算法, 笔记]
downloadable: true
---
# 哈希：

1.数组构建

2.set构建

3.map构建

## 最长子序列

[128. 最长连续序列 - 力扣（LeetCode）](https://leetcode.cn/problems/longest-consecutive-sequence/description/?envType=study-plan-v2&envId=top-100-liked)

### 暴力代码

```python
class Solution:
    def longestConsecutive(self, nums: list[int]) -> int:
        nums.sort()
        n=len(nums)
        st=[]
        if(len(nums)==0):
            return 0
            
        st.append(nums[0])
        for i in range(1,n):
            if(nums[i]!=nums[i-1]):
                st.append(nums[i])
            else:
                continue
        l=1
        ans=0
        t=1
        for i in range(1,len(st)):
            if(st[i]!=st[i-1]+1):
                ans=max(l,ans)
                l=1
            else:
                l+=1
        ans=max(l,ans)
        return ans
```

### 优化：

首先，本题是不能排序的，因为排序的时间复杂度是 `O(nlogn)`，不符合题目 O(n) 的要求。

核心思路：对于 `nums` 中的元素 x，以 x 为起点，不断查找下一个数 `x+1,x+2,x+3,…` 是否在 `nums` 中，同时统计连续序列的长度。

为了做到 O(n) 时间复杂度，需要两个关键优化：

> [!CAUTION]
>
> 1. 把 `nums` 中的数都放入一个**哈希**集合中，这样可以 `O(1)` 判断一个数是否在 `nums` 中。
>
> 2. 如果 `x−1` 在哈希集合中，则不以 `x` 为起点。为什么？因为以 **`x−1` 为起点计算出的序列长度，一定比以 x 为起点计算出的序列长度要长**！这样可以避免大量重复计算。比如 `nums=[3,2,4,5]`，从 3 开始，我们可以找到 `3,4,5` 这个连续序列；而从 `2` 开始，我们可以找到 `2,3,4,5` 这个连续序列，一定比从 3 开始的序列更长。
>
>    **⚠注意：遍历元素的时候，要遍历哈希集合，而不是 `nums`！**如果 `nums=[1,1,1,…,1,2,3,4,5,…]`（前一半都是 1），遍历 `nums` 的做法会导致每个 1 都跑一个 O(n) 的循环，总的循环次数是 O(n ^2)，会超时

作者：灵茶山艾府
链接：https://leetcode.cn/problems/longest-consecutive-sequence/solutions/3005726/ha-xi-biao-on-zuo-fa-pythonjavacgojsrust-whop/

```python
class Solution:
    def longestConsecutive(self, nums: list[int]) -> int:
        #哈希集合：基于哈希表实现 1.无序，2.去重，3.时间复杂度<O(log(n))
        st=set(nums)
        ans=0
        #以 x−1 为起点计算出的序列长度，一定比以 x 为起点计算出的序列长度要长
        #确定起点是x
        for x in st:
            if x-1 in st:
                continue
            #找到每一个x对应的终点
            y=x+1
            while y in st:
                y+=1
            ans=max(ans,y-x)
        return ans
```

知识点补充：

#### 哈希集合（set）

**基于哈希表实现 1.无序，2.去重，3.时间复杂度<O(n)**

- `add(x)`：加入元素，已存在则返回 false
- `contains(x)`：判断是否存在（算法题最常用）
- `remove(x)`：删除元素
- `size()`：元素个数
- `clear()`：清空

小优化：设 m 为 nums 中的不同元素个数（即哈希集合的大小）。各个连续序列（链）是互相独立的，如果我们发现其中一条链的长度至少为  `2m`（长度乘 `2` 大于等于 `m`），由于不可能还有一条长度大于  `2m`的链（否则这两条链的长度之和就超过 `m` 了），答案不会再增大，此时可以直接返回答案。

作者：灵茶山艾府
链接：https://leetcode.cn/problems/longest-consecutive-sequence/solutions/3005726/ha-xi-biao-on-zuo-fa-pythonjavacgojsrust-whop/

错误代码：

```
class Solution:
    def longestConsecutive(self, nums: list[int]) -> int:
        st=set(nums)
        n=len(st)
        ans=0
        for x in st:
            if x-1 in st:
                continue
            y=x+1
            while y in st:
                y+=1
            ans=max(ans,y-x)
            if ans*2>=n :
                return ans
```

```python
#输入：[]
#输出：null
#预期：0
```

**原因：[] 无ans 不执行 return ans 返回 null**

正确代码：

```python
class Solution:
    def longestConsecutive(self, nums: list[int]) -> int:
        st=set(nums)
        n=len(st)
        ans=0
        for x in st:
            if x-1 in st:
                continue
            y=x+1
            while y in st:
                y+=1
            ans=max(ans,y-x)
            if ans*2>=n :
                break        
        return ans
```



## 字母异或词分组

总体思路，构建哈希找相同的值作为键，最后的值即为答案。

[49. 字母异位词分组 - 力扣（LeetCode）](https://leetcode.cn/problems/group-anagrams/description/?envType=study-plan-v2&envId=top-100-liked)

### 排序+哈希

由于互为字母异位词的两个字符串包含的字母相同，故可以将排序之后的字符串作为哈希表的键

[^不可作为字典的键]:

本质：可变对象，内容能修改，哈希值会变

- `list` 列表！sorted(st)` 返回的就是 list，不能直接做 key）->转换str
- `dict` 字典本身
- `set` 普通集合

```python
class Solution:
    def groupAnagrams(self, strs: list[str]) -> list[list[str]]:
        d={}

        n=len(strs)
        if(n==1):
            return [strs]
        else:
            for st in strs:
                s=str(sorted(st))
                if s not in d:
                    #初始创个列表为值
                    d[s]=[st]
                else:
                    #值列表加元素
                    d[s].append(st)
            return list(d.values())
            
```

初始：

```python
d = {}
n = len(strs) = 6
n != 1 → 进入 else，开始 for 循环
```

第 1 次循环：`st = "eat"`

- `sorted("eat")` → `['a','e','t']`
- `s = str(['a','e','t'])` → `"['a', 'e', 't']"`
- `s` 不在字典 `d` 里： `d["['a', 'e', 't']"] = ["eat"]`

```
d = {
  "['a', 'e', 't']": ["eat"]
}
```

第 2 次循环：`st = "tea"`

- `sorted("tea")` → `['a','e','t']`
- `s = "['a', 'e', 't']"`
- key 已经存在，追加： `d["['a', 'e', 't']"].append("tea")`

```
d = {
  "['a', 'e', 't']": ["eat", "tea"]
}
```

#### 精简写法

`defaultdict` 是 `collections` 里的字典，访问不存在的键时会自动创建默认值。

```python
from collections import defaultdict
```

```python
class Solution:
    def groupAnagrams(self, strs: list[str]) -> list[list[str]]:
        d = defaultdict(list)

        for st in strs:
            
            k = "".join(sorted(st))
            d[k].append(st)

        return list(d.values())
```

`defaultdict(list)`，如果访问一个不存在的 key，会自动帮你创建，默认值是空列表 `[]`，不用手动写 `if key not in d`

1. `st = "eat"`

- `sorted("eat")` → `['a','e','t']`
- `k = "".join(...)` → `"aet"`
- `d["aet"]` 不存在 → 自动生成 `[]`，然后 `append("eat")`

```python
d["aet"] = ["eat"]
```

1. `st = "tea"`

- `sorted("tea")` → `['a','e','t']`
- `k = "aet"`
- `d["aet"]` 已经是 `["eat"]`，追加

```python
d["aet"] = ["eat", "tea"]
```

计数+哈希

显然每个字母出现的次数相等，互为异或词；所以可以把cnt记录字母位置个数，相同，作为键->值

```python
class Solution:
    def groupAnagrams(self, strs: list[str]) -> list[list[str]]:
        d=defaultdict(list)
        for st in strs:
            cnt=[0]*26
            for ch in st:
                cnt[ord(ch)-ord("a")]+=1
            d[tuple(cnt)].append(st)
        return list(d.values())
```

**d[tuple(cnt)]：d哈希 ，cnt是列表，可变，不可以作为键，要转换为tuple元组**

### 补充

[242. 有效的字母异位词 - 力扣（LeetCode）](https://leetcode.cn/problems/valid-anagram/description/)

排序：非常简单sort直接实现

#### 哈希：

```python
class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        hash=[0]*26
        for i in s:
            hash[(ord(i)-ord("a"))]+=1
        for j in t:
            hash[(ord(j)-ord("a"))]-=1
        flag=0
        for i in range(26):
            if(hash[i]!=0):
                return False
        return True
```

