LeetCode Hot 100 · 哈希

LeetCode Hot 100 · 哈希

2026年11月19日·#笔记LeetCode/算法/笔记·1293 字 6 分钟
下载 Markdown
AI 摘要- DeepSeek

LeetCode Hot 100 哈希专题:数组 / set / map 三种构建方式,以及最长连续序列从暴力到 O(n) 的优化思路

哈希:#

1.数组构建

2.set构建

3.map构建

最长子序列#

128. 最长连续序列 - 力扣(LeetCode)

暴力代码#

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/

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
#输入:[]
#输出:null
#预期:0

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

正确代码:

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)

排序+哈希#

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

本质:可变对象,内容能修改,哈希值会变

  • list 列表!sorted(st)` 返回的就是 list,不能直接做 key)->转换str
  • dict 字典本身
  • set 普通集合
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())

初始:

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 里的字典,访问不存在的键时会自动创建默认值。

from collections import defaultdict
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")
d["aet"] = ["eat"]
  1. st = "tea"
  • sorted("tea") → ['a','e','t']
  • k = "aet"
  • d["aet"] 已经是 ["eat"],追加
d["aet"] = ["eat", "tea"]

计数+哈希

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

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)

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

哈希:#

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
Python 语法与算法学习
我的博客搭建记

评论区

评论 0

昵称和内容会公开显示
    [ 音乐 ]
    封面

    音乐

    暂未播放

    0:000:00
    暂无歌词
    [ 壁纸 ]
    模式
    透明度55%
    全站壁纸
    首页壁纸

    全站壁纸和首页壁纸可分别设置,默认亮暗主题壁纸保持不变;图片仅保存在本机浏览器。

    [ 首页文案 ]

    保存后首页立即生效,仅保存在本机浏览器。

    找不到相关结果。
    [ contents ]
    [ 全部文章 ]