第一天还在用暴力双循环秒过简单题到了第四天进入哈希很多人会突然卡住——题仿佛全见过但一写就不知道哈希表里到底该存什么、什么时候存、存了之后怎么还往回找。这篇就针对“速通Hot100-Day04——哈希”这个主题把哈希类题目的识别方法、核心推导、常见模型、实战踩坑和刷题顺序一次性讲透。适合正在按Hot100刷题的人、准备面试前突击哈希题的人也适合那些刷了几道题但始终停留在“背题解”状态的选手。看完你会发现哈希题不是靠记题号而是靠学会建模。1. 为什么Hot100的第四天要集中过一遍哈希1.1 哈希在算法题里的定位是“查找加速器”哈希表Hash Table本质上是一个数组加散列函数的结构。你把一个键交给散列函数它算出下标然后直接落到数组的某个位置冲突时再通过拉链法或开放寻址法处理。这个结构带来的核心收益是查找、插入、删除的平均时间复杂度都接近 O(1)。对比一下几种常见容器操作数组/列表哈希表查找一个元素O(n)O(1) 平均统计元素频次O(n) 每查一次都要扫O(1) 更新判断重复O(n) 需要额外标记O(1) 插入时判断按大小顺序遍历O(n) 且有序无序不能依赖顺序后台同学可能会问数组下标查找不是也 O(1) 吗是的但哈希表的贡献在于把原本无法用下标表达的东西变成下标。比如字符串、对象、自定义键通过哈希函数都能映射成整数。这就是为什么很多题一开始看不出和哈希有关最后优化方案里都站着哈希表。1.2 第四天这个位置有它的道理如果你按大多数刷题路线走第一天通常是数组和链表第二天是栈和队列第三天是二分查找或者排序。到第四天安排哈希是因为它需要一点前置能力你要先理解数组索引的意义理解时间复杂度对比理解“空间换时间”这个概念。哈希不是独立的技术它更像一个“元能力”——后面几乎所有题都可能用到它来提速。我在刷到后面二叉树、图相关的题目时经常回头用哈希解决一些分支判断。比如树的横向比较、图的访问标记本质上都是哈希的变形。所以第四天把哈希打扎实后面能省很多事。1.3 一眼判断“这题需要哈希”我在刷Hot100时总结了一套“题眼识别法”满足以下任意一条基本就往哈希方向想需要找一个元素的“另一半”例如“两数之和”“四数相加”需要统计频次或者计数例如“字母异位词分组”“出现次数最多的元素”需要快速去重例如“最长连续序列”需要记住某个值上一次出现的位置例如“无重复字符的最长子串”。但注意哈希也不是万能。如果数组本身有序两数之和更优解是双指针空间 O(1)如果数据范围很小直接用数组计数可能比哈希更快。所以准确的说法是当你面对无序数据且需要高频查找、计数、去重时哈希是首选。2. 从“暴力双循环”到“一次遍历”哈希的优化思路完全可以推导2.1 两数之和先查再存避免同一个元素重复用这是哈希最经典的入门题。暴力版本是两层循环枚举 i 和 j复杂度 O(n²)。哈希版本的核心思路是我每走到一个数 num我需要的是 target - num 之前有没有出现过。那就把已经路过的数存进哈希表一边走一边查。def twoSum(nums, target): seen {} for i, num in enumerate(nums): need target - num if need in seen: return [seen[need], i] seen[num] i return []这里有个非常容易被新手忽略的点必须先查再存不能先把所有数一次性存进哈希表再查。如果先全部存进去当你查 target - num 时可能会把当前这个 num 自己也算进去。比如 nums [3, 3], target 6如果先存完再查哈希表里第二次遇到 3 时查到 need 3 已经存在会返回同一个下标。而“先查再存”就能保证找到的两个下标一定不同。2.2 和为 K 的子数组前缀和配哈希计数而不是滑动窗口这题也是Hot100哈希区里很容易让人翻车的题。很多人第一反应是“连续子数组那我用滑动窗口”直接踩坑。滑动窗口能成立的前提是数组单调变化一旦数组里有负数窗口长度的增减和窗口和之间的关系就不可控了。正确姿势是前缀和。设 pre[i] 表示数组前 i 个元素的和那么子数组 nums[j1] 到 nums[i] 的和就是 pre[i] - pre[j]。题目要求这段和等于 k等价于找 pre[i] - pre[j] k也就是 pre[j] pre[i] - k。于是问题变成遍历到当前位置 i 时历史前缀和里有多少个值等于 pre[i] - k。from collections import defaultdict def subarraySum(nums, k): cnt defaultdict(int) cnt[0] 1 # 前缀和为0的情况代表从下标0开始的子数组 prefix 0 ans 0 for x in nums: prefix x ans cnt[prefix - k] cnt[prefix] 1 return ans细节在于 cnt[0] 1 的初始化它表示“在还没有任何元素时前缀和为 0 出现过一次”。这对应着整个数组从第 1 位到当前位置恰好构成和为 k 的子数组的场景。另外为什么是边遍历边更新计数而不是先全部计数再遍历因为子数组有方向性j 必须在 i 之前如果提前把所有前缀和都放进哈希表可能会错误统计到“未来”的前缀。2.3 两次遍历和一次遍历怎么选很多Hash题都有“先完整建表”和“边遍历边查”两种写法选择标准很简单答案是否依赖元素之间的相对顺序。两数之和依赖“两个元素是不同下标”所以要边查边存。字母异位词分组则需要把整个字符串数组扫完按 key 聚成一类天然适合先建表再输出。来看一个标准解法from collections import defaultdict def groupAnagrams(strs): groups defaultdict(list) for s in strs: key .join(sorted(s)) groups[key].append(s) return list(groups.values())核心思路是让所有异位词经过某种变换后得到同一个 key。这里用“排序后的字符串”做 key简单直接如果追求更低的复杂度可以用一个长度为 26 的频次数组编码成字符串。但编码时要注意如果直接用 list 计数作为 key 会报错因为 list 不可哈希需要转成 tuple 或字符串。3. Day04刷下来哈希题型基本就这三类模型3.1 计数模型value 是次数统计频率或聚合同类这个模型的典型特征是“这类元素长得不一样但本质相同”。就像字母异位词分组abc、bca、cab 排序后都是 abc所以会归到同一个组。另一道典型题是“最长连续序列”def longestConsecutive(nums): num_set set(nums) longest 0 for num in num_set: if num - 1 not in num_set: cur num cur_len 1 while cur 1 in num_set: cur 1 cur_len 1 longest max(longest, cur_len) return longest这里用到 HashSet 去重并把 O(n) 的连续扩展过程控制成每个数只被扩展一次。关键技巧是只从“连续序列的起点”开始扩展。怎么判断起点当前数字 num 的前一个 num-1 不在集合里。如果不加这个判断每个数都可能作为中间数向外扩展整体会退化成 O(n²)。3.2 定位模型value 是下标或位置记录“上一次在哪出现”这类题的价值在于哈希表不仅告诉你“有没有”还告诉你“在哪”。典型代表是“无重复字符的最长子串”。配合滑动窗口用哈希表记录每个字符最近一次出现的下标遇到重复字符时更新左边界。def lengthOfLongestSubstring(s): last {} left 0 ans 0 for i, ch in enumerate(s): if ch in last and last[ch] left: left last[ch] 1 last[ch] i ans max(ans, i - left 1) return ans这个解法的精妙点在于更新左边界时必须用last[ch] left判断而不是一遇到ch in last就直接更新。原因很实际——哈希表里存的可能是很久之前出现的旧下标那个下标已经不在当前窗口范围里直接用会把左边界往回拉。3.3 去重与缓存模型只关心“存在不存在”或者需要顺序纯去重类模型最简单直接 HashSet 判断即可。难一点的是把哈希和链表结合比如 LRU 缓存。这个题不单纯考哈希但哈希部分承担了“O(1) 定位节点”的职责双向链表承担“维护访问顺序”的职责。实现思路是哈希表的 key 存缓存键value 存双向链表节点每次 get如果命中把节点移动到链表头部每次 put如果容量满了删除链表尾部节点再在头部插入新节点。没有哈希表单靠链表找节点需要 O(n)有了哈希表节点定位变成 O(1)。这类题告诉我们的模型价值是哈希表可以和其他数据结构组合解决“快速找到”加“有序维护”的组合需求。4. 真实的坑比题目本身更值得记录4.1 哈希表的无序性会杀死很多“想当然”哈希表内部通过散列函数寻址遍历顺序取决于哈希函数和插入位置而不是你塞进去的顺序。哪怕 Python 3.7 之后的 dict 保证了插入有序那也只是语言实现层面的额外承诺不能在所有场景里依赖它。刷题时如果题目对输出顺序有要求一定额外排序或按原顺序组装不要赌哈希表遍历顺序。4.2 重复元素的覆盖问题更新 value 前先想清楚旧值还重不重要拿“无重复字符的最长子串”来说同一个字符会反复出现哈希表里的旧下标有时要保留有时要忽略。我的判断方法是value 里存的必须是“当前窗口内最近一次出现的位置”而不是“历史最近一次”。一旦 left 移动到了旧下标之后旧下标就不能再参与边界计算所以要靠last[ch] left兜底。另一个常见场景是“两数之和”里如果数组有重复值后一个相同值会覆盖前一个下标但你要找的是任意一对解覆盖后不影响正确性。所以覆盖本身没问题问题是你是否清楚覆盖的时机和影响。4.3 键类型与相等性判断看着一样的键可能不是同一个键这个坑在不同语言里表现不同。Python 里要特别注意1和True会被当成同一个键因为1 True且 hash 相同。如果你用布尔值作为 key 又恰好存在整数 1逻辑会乱。Java 里要小心 Integer 和 Long 的 equals 语义以及 HashMap 和 Hashtable 对 null 键的限制差异。还有一个细节很多自定义对象如果重写了 equals 却没有重写 hashCode会导致两个逻辑上相等的对象被放进哈希表的不同位置查的时候永远查不到。刷题时一般不会遇到自定义对象但面试里经常会问。4.4 传说中的 O(1) 也不是完全免费哈希表平均是 O(1)但最坏情况下大量元素碰撞查找会退化。刷题平台的数据一般不会刻意构造针对 Python 默认哈希的攻击数据但你心里要清楚如果自己实现哈希函数冲突处理不好复杂度可能比暴力还差。容量扩容也需要成本所以有些超高实时性场景会“预热”容量。竞赛和面试里真正要理解的是哈希不是银弹它是用额外空间换时间空间复杂度通常是 O(n)所以空间受限的题要慎用。5. Day04的速通打法题目顺序、时间盒与复盘清单5.1 推荐的刷题顺序与时间分配我习惯按“模型难度”排序而不是按题目编号排序。第4天可以直接采用下面这套顺序每道题设置时间盒超时先看题解再独立写一遍顺序题名建议时间当天目标1两数之和20分钟理解“先查后存”2字母异位词分组20分钟掌握 key 的构造3无重复字符的最长子串30分钟掌握左边界更新条件4和为K的子数组35分钟前缀和转成哈希计数5最长连续序列30分钟去重 起点扩展总时间控制在两个半小时左右。如果做完这些还有余力可以把“四数相加”也过一遍它是两数之和模型的扩展版。5.2 一张“哈希卡”的复盘方法我发现光刷题不复盘三天后等于没刷。所以第四天会要求自己为每道题写一张“哈希卡”字段固定题名判断的模型key 存什么value 存什么是边遍历边更新还是先建表最容易错的边界点。拿前面的题举例三张卡大致是两数之和定位模型key target-numvalue 下标边查边存坑是当前元素不能自己匹配自己和为K的子数组计数模型key 前缀和value 出现次数边算前缀和边统计坑是 cnt[0] 初值必须为 1无重复字符的最长子串定位模型key 字符value 最近出现下标边遍历边更新左边界坑是last[ch] left判断不可丢。这卡不需要工整写给自己看就行。第二天开始刷题前先扫一眼三天后合上笔记手写一遍代码能写出来才是真的掌握了。5.3 判断自己是否真的会了三连问我在刷完第四天内容后会给自己做一次“三连问”自检**原暴力解法复杂度多少当前哈希解法复杂度多少**如果答不上来说明还没理解“哈希优化在优化什么”。**如果输入数据里有负数、重复元素、无序排列这个解法还成立吗**这是为了锻炼边界思维。例如和为K的子数组有负数时滑动窗口不能用的原因要能一句话说清。**如果把这里的 value 存的内容从“次数”改成“下标”题目会变成什么样子**这是最值钱的一问。它逼着你在两数之和、字母异位词分组、无重复字符最长子串之间建立联系而不是背题号。这套三连问做下来大概每道题多花十分钟但效果比多刷十道题都明显。最后说点个人体会。Hot100的哈希专题难点从来不是哈希表本身而是“什么时候意识到该用哈希”。我在第四天刷完之后最大的收获不是会做这几道题而是学会了一个公式遇到无序数据的查找、计数、去重、定位先无脑往哈希方向建模再用复杂度分析验证是否真的需要。建议你第4天结束后隔一天再花三十分钟把两数之和、和为K的子数组、最长连续序列这三道题重写一遍手感和记忆会完全不一样。