很多刷题的人走到 Day09第一次会有点“这天的题也太简单了吧”的错觉。349 和 350 看起来都是求交集438 看起来也只是一个字符串匹配变体如果只是把答案抄一遍、过一遍用例那这一天的真实价值基本就漏掉了。这三道题放在一起并不是凑数它们刚好构成了一条完整的哈希表学习路径Set 判断存在、Map 统计次数、数组做字符频次表再配合滑动窗口。也就是说同一个数据结构在不同问题约束下会演化出三种完全不同的用法。这篇文章我就把三道题从原理到代码到易错点完整拆开一次讲清楚。1. 为什么这三道题要放在同一天哈希表的三种角色先说一个我自己刷代码随想录时的感受Day09 之前的内容大多在训练“怎么遍历”到了 Day09 才开始训练“怎么查找”。349 和 350 本质上是同一种问题的两个难度等级而 438 又是在它们基础上多叠了一个“窗口移动”的维度。把三道题放在一起核心目的只有一个让你体会到哈希表在不同场景下承担的不同职责。用一个表来总结会很直观题目使用的哈希结构核心任务时间复杂度349. 两个数组的交集HashSet判断元素是否存在O(n m)350. 两个数组的交集ⅡHashMap 计数统计并匹配出现次数O(n m)438. 找所有字母异位词数组长度为 26维护窗口内字符频次并和基准比较O(n) 或 O(n * 26)注意第三题我没有用 Map而是选了长度为 26 的数组。原因很实际字母异位词的字符集是固定的小写字母用数组可以直接通过ord(c) - 97做下标访问既没有哈希计算的常数开销也不存在扩容问题。这是面试里很加分的细节很多人只记得“用哈希表”却不知道哈希表的三个形态怎么选。1.1 哈希表真正解决的是什么问题在没有哈希表的世界里要判断两个数组是否有交集最直接的想法是双重循环拿第一个数组的每个元素去第二个数组里扫一遍。复杂度是 O(n * m)当 n 和 m 都到 10 的 5 次方级别时这个复杂度就是灾难。哈希表做的事情是“预索引”。你先把其中一组数据放进一个查找表之后每一次“这个元素在不在”的判断都从“扫一遍”变成“点一下”。这种预计算思想在算法题里无处不在。你可以把它类比成图书馆查书没有索引的时候你得一本一本翻有了索引卡直接翻到对应位置就行。哈希表就是那张索引卡。1.2 三题串联起来的解题主线这三道题的进阶逻辑很清晰可以串成一条线349 教会你“用 Set 保存已经出现过的元素”350 教会你“用 Map 记录元素出现的次数”438 教会你“用一张频次表作为比较基准并用指针在长字符串上平移窗口”。从前两题的一锤子买卖到第三题的动态维护这才是 Day09 的真正主线。理解了这条线你后续做 76 题最小覆盖子串、567 题字符串排列的时候会发现套路几乎是复刻的。2. 349. 两个数组的交集去重才是这道题的主角题目非常简单给定两个数组返回它们的交集输出结果中的每个元素必须是唯一的顺序不限。很多新手看完题目立刻说“这不就两层循环找相同的吗”能这么做但会踩到两个坑一是重复元素会让结果数组出现重复二是复杂度不达标。2.1 为什么要一边用 Set而不是直接遍历收集看个例子就明白了nums1 [1, 2, 2, 1]nums2 [2, 2]。直接遍历 nums1查找 nums2 是否包含当前元素你会把两个 2 都收集进去得到[2, 2]但题目要求输出唯一值[2]。所以这道题真正的主角不是“查找”是“去重”。去重有两个办法一个是把结果放进 Set利用其天然去重特性另一个是用一个单独的seen数组在加入结果时做一次判断。两种写法都可以但面试的时候我更推荐第二种因为你能顺势展示你对重复来源的理解。2.2 标准解法与代码逐行拆解class Solution: def intersection(self, nums1: List[int], nums2: List[int]) - List[int]: set1 set(nums1) ans [] seen set() for x in nums2: if x in set1 and x not in seen: seen.add(x) ans.append(x) return ans逻辑很清楚先把 nums1 转成 Set这一步的复杂度是 O(n)同时去重然后遍历 nums2判断x是否在 set1 中存在同时检查它是否已经在答案里出现过。seen这个 Set 只用 O(k) 的空间k 是交集元素个数。当然Python 里也可以一行写return list(set(nums1) set(nums2))这个写法在竞赛和日常刷题中没问题但如果你是在面试建议先写出手动遍历版本再提一句“也可以用语言内置的集合并集操作”。这样比直接拍出一行代码更稳妥因为面试官能从手动版本里看到你的去重意识。2.3 排序后的双指针解法如果题目额外说明“数组已经有序”还有一个很有意思的解法排序双指针。事实上即使没有排序你也可以先排序再做双指针代价是多出 O(n log n m log m) 的排序时间。class Solution: def intersection(self, nums1: List[int], nums2: List[int]) - List[int]: nums1.sort() nums2.sort() i j 0 ans_set set() while i len(nums1) and j len(nums2): if nums1[i] nums2[j]: ans_set.add(nums1[i]) i 1 j 1 elif nums1[i] nums2[j]: i 1 else: j 1 return list(ans_set)双指针的思路是两个数组都从小到大走谁小谁先走。相等的时候收集结果。这里我特意用了ans_set而不是直接ans.append因为双指针本身不会跳过连续重复元素。比如nums1 [1, 1, 2]nums2 [1, 3]第一次匹配到 1 之后i和j都后移但i指向的还是 1j已经指向 3这时候不会重复收集可如果两边都有连续重复比如nums1 [1, 1]nums2 [1, 1, 1]双指针会连续匹配到两次 1所以必须用 Set 去重。2.4 这道题的边界检查空数组任何数组为空时交集为空代码里 while 循环或 Set 交集自然处理。重复元素上面已经演示过这是最核心的坑。返回类型题目要求返回数组而不是 Set记得转换。3. 350. 两个数组的交集Ⅱ从“有”到“有几个”349 问的是“存不存在”350 问的是“有几个”。这个变化听起来很小但它直接改变了数据结构的选择你需要用 Map 来计数。题目要求输出两个数组中共同出现元素的次数而且重复次数要取较小值。比如nums1 [1, 2, 2, 1]nums2 [2, 2]结果是[2, 2]因为 2 在第一个数组出现两次在第二个数组也出现两次。3.1 计数匹配的核心思想思路是把其中一个数组的元素统计成“元素 - 次数”的 Map然后遍历另一个数组每遇到一个在 Map 中还有余量的元素就把它收集进结果同时把 Map 里对应的计数减一。这个过程很像“对账”一边记着库存数量另一边消耗库存能消耗到几次就输出几次。class Solution: def intersect(self, nums1: List[int], nums2: List[int]) - List[int]: # 优先把较短的数组哈希化节省空间 if len(nums1) len(nums2): nums1, nums2 nums2, nums1 cnt {} for x in nums1: cnt[x] cnt.get(x, 0) 1 ans [] for x in nums2: if x in cnt and cnt[x] 0: ans.append(x) cnt[x] - 1 return ans这段代码里有个小技巧先把较短的那个数组变成 Map。因为空间复杂度是 O(min(n, m))选短的自然更省。有人可能会问选长的会怎样不会出错但空间多一倍没必要。这种细节在面试里说一句“我这里优先把短数组哈希化是为了把空间复杂度压到 O(min(n, m))”加分效果很明显。另一个值得注意的点是判断条件cnt[x] 0。因为遍历过程中某个元素的计数可能已经被扣到 0这时候即使 x 还在 Map 里也应该跳过。如果漏掉这个条件结果数组里会出现多余的重复项。3.2 为什么不能用 Set 替代 Map用一个简单例子说明nums1 [1, 1, 1]nums2 [1, 1]。如果只判断存在性你会把两个 1 都放进去吗不会因为你只判断了一次“1 在不在”然后就把 1 加入了结果但并不知道第二个 1 是否能继续匹配。所以“有几个”类的问题必须把“还有几个”记下来。这就是 Map 和 Set 的分界线Set 回答“有无”Map 回答“多少”。3.3 有序数组下的双指针版本和 349 一样这题也有双指针解法但注意它不需要再去重了因为重复次数本身就是要保留的信息。class Solution: def intersect(self, nums1: List[int], nums2: List[int]) - List[int]: nums1.sort() nums2.sort() i j 0 ans [] while i len(nums1) and j len(nums2): if nums1[i] nums2[j]: ans.append(nums1[i]) i 1 j 1 elif nums1[i] nums2[j]: i 1 else: j 1 return ans你会发现这段代码和 349 的双指针版本几乎一样唯一差别是结果收集这里用了ans.append而不是ans_set.add。为什么 350 不需要去重因为双指针每一次匹配到的都是当前指针位置上的元素两个数组都有序连续相同的元素会被连续匹配而连续匹配恰好就对应了“重复出现次数取较小值”的语义。3.4 两道交集题放在一起的对比维度349350输出要求去重后唯一值保留重复次数哈希结构SetMap 计数双指针去重需要 Set不需要核心考察点存在性 去重频次匹配这一步对比做好了后面再做 349 和 350 的变体题基本都不慌。4. 438. 找到字符串中所有字母异位词滑动窗口的第一道门槛先说结论438 是“滑动窗口 固定长度”的经典模板题。它的难度不在于哈希表本身而在于“如何在窗口移动时高效维护频次信息”。理解了这一题后面 567 题字符串的排列、76 题最小覆盖子串都会顺很多。题目是这样给定两个字符串 s 和 p找到 s 中所有 p 的异位词的起始索引。所谓异位词其实就是“字符相同、排列顺序不同”的子串比如 p “abc”那么 “bca”、“cab” 都是它的异位词。4.1 为什么暴力解法必挂最直觉的做法是对 s 的每一个下标切出长度为 len(p) 的子串然后判断它和 p 的字符频次是否相同。判断频次可以用排序后比较也可以用 26 长度的数组去比对。但这个做法的时间复杂度是 O(n * m * 26)n 是 s 长度m 是 p 长度。当 n 和 m 到 10 的 4 次方级别时这个复杂度直接超时。核心问题出在相邻两个子串之间其实有大量重叠字符暴力解法把每个子串都当作独立问题重新计算了一遍。滑动窗口的思路恰恰是把“重复计算”的部分利用起来窗口每次只挪一格只动头尾两个字符中间的信息全部保留。4.2 固定窗口的移动流程这道题窗口大小固定为 len(p)不需要动态伸缩。我们可以先把窗口初始化为 s 的前 len(p) 个字符然后每次向右移动一格右侧字符进入窗口左侧字符离开窗口。再用一个 26 长度的数组记录窗口内每个字符的出现次数和 p 的频次表比对。直接看代码class Solution: def findAnagrams(self, s: str, p: str) - List[int]: n, m len(s), len(p) if n m: return [] need [0] * 26 for ch in p: need[ord(ch) - 97] 1 window [0] * 26 for i in range(m): window[ord(s[i]) - 97] 1 ans [] if window need: ans.append(0) for i in range(m, n): # 右侧新字符进入窗口 window[ord(s[i]) - 97] 1 # 左侧旧字符离开窗口 window[ord(s[i - m]) - 97] - 1 if window need: ans.append(i - m 1) return ans这里最容易被忽视的是第 26 行和第 29 行的顺序。先加新字符还是先减旧字符其实对于固定长度的窗口两者结果都一样因为窗口长度一直保持 m 不变。但为了形成肌肉记忆我建议统一“先加后减”这样在以后做可变窗口时不容易混。这个版本的复杂度是 O(n * 26)因为每次移动后都要比较两个长度 26 的数组。在 n 是 10 的 5 次方时大约 260 万次操作完全够用。但如果你想要更极致一点可以把每次 O(26) 的比较压缩成 O(1)。4.3 用 differ 变量把比较优化到 O(1)炒股的人看盯盘滑动窗口优化的关键是只关注“变化的部分”。窗口每次移动时只有右侧进入的字符和左侧离开的字符会改变频次所以我们只需要维护一个变量differ表示当前窗口频次和 target 频次之间有多少个位置不一致。当differ 0时就找到了一个异位词。这个优化思路在面试里很常见属于“你比普通解题者多想了一步”的亮点。代码长一点但值得吃透class Solution: def findAnagrams(self, s: str, p: str) - List[int]: n, m len(s), len(p) if n m: return [] need [0] * 26 window [0] * 26 for ch in p: need[ord(ch) - 97] 1 for i in range(m): window[ord(s[i]) - 97] 1 def count_diff(): return sum(1 for i in range(26) if need[i] ! window[i]) differ count_diff() ans [] if differ 0: ans.append(0) for i in range(m, n): # 新字符进入窗口 idx ord(s[i]) - 97 old_val window[idx] window[idx] 1 if old_val need[idx]: differ 1 elif window[idx] need[idx]: differ - 1 # 旧字符离开窗口 idx_out ord(s[i - m]) - 97 old_val_out window[idx_out] window[idx_out] - 1 if old_val_out need[idx_out]: differ 1 elif window[idx_out] need[idx_out]: differ - 1 if differ 0: ans.append(i - m 1) return ansdiffer 的更新逻辑可能有点绕核心就一句话只有当某个字符在变化前后和 need 的关系发生了“从相等变为不相等”或“从不相等变为相等”时differ 才需要调整。比如window[idx]原来是 2need[idx]也是 2这一格是匹配的新字符进来后window[idx]变成 3这一格就不匹配了所以differ 1。反过来如果原来是 3目标是 2进来一个字符变成 4还是不等于 2那差还是差differ不用动。4.4 固定窗口和可变窗口的选择判断很多初学者学滑动窗口时最大的困惑是什么情况下用固定窗口什么情况下用可变窗口。我给一个简单粗暴的判断标准窗口大小是不是题目里给定的常数。如果是那就是固定窗口比如本题窗口长度必须等于 len(p)如果题目让你“找最短子串”“找最长子串”窗口大小是随条件动态伸缩的那就是可变窗口。固定窗口的模板通常是初始化窗口到起点移动右指针纳入新元素移动左指针一格踢出旧元素判断当前窗口是否满足条件可变窗口的模板则一般是右指针一直走纳入新元素当窗口不满足条件时移动左指针收缩窗口直到满足条件在收缩过程中更新答案这两个模板不要混着用否则很容易出现左右指针不同步的 bug。4.5 边界条件和常见报错438 这道题我见过很多人踩坑挑几个典型的p 比 s 长这种情况直接返回空列表很多人在代码开头忘了判断。起始索引 0窗口初始状态可能就已经是异位词需要单独判断别漏掉。ord 用的是 97 还是ord(a)写成ord(ch) - ord(a)可读性更强但 97 也行只是为了少一次函数调用。更新顺序建议固定“先加后减”一旦写反窗口内字符频次在中间状态会错乱。5. 刷完这三题后应该沉淀下来的哈希表选型框架这三道题如果只是背代码过两天就忘。真正应该沉淀的是“遇到什么样的题选什么样的哈希表”这个决策能力。我把自己常用的判断路径整理一下。5.1 遇到交集/子串问题时怎么思考这是一个决策链只判断存在与否用 Set。需要统计次数、索引位置用 Map。字符集很小且范围固定比如 26 个小写字母用数组不用 Map省掉哈希开销。子串长度固定并且要做频次匹配用“固定窗口 数组”。题目要求最短/最长子串用“可变窗口 Map 或数组”。这个决策链不是背出来的而是从这三道题中自然长出来的。349 让你明白什么是存在性350 让你明白计数和扣减438 让你明白窗口移动时如何增量更新状态。三者合起来就是一个完整的哈希表应用拼图。5.2 复杂度边界和数据范围分析做算法题复杂度估算不能靠感觉。拿 438 的暴力解来说n 3 * 10^4m 2 * 10^4暴力的比较次数是 n * m * 26大约是 1.56 * 10^10肯定超时。而滑动窗口的 O(n * 26) 版本大概是 7.8 * 10^5两个数量级完全不一样。所以在动手写代码前先看一眼数据范围如果 n 和 m 都到 10^5暴力 O(n * m) 一定不可行这时候用哈希表把查找降到 O(1)复杂度就是 O(n m)这是非常标准的优化路径。面试时可以先说“暴力是 O(n*m)我用哈希表把每个元素的查找代价降下来总体是 O(nm)”这就是一个完整的复杂度分析闭环。5.3 面试时的表达顺序很多人代码写得出来但面试讲得乱。建议按照这个顺序先讲题意和输入规模点出暴力解法的问题。再讲优化思路用什么数据结构为什么选它。然后画一下流程窗口怎么移动Map/Set 怎么维护。最后写代码边写边解释每一步在干什么。测试样例也要会自己构造空数组、全相同数组、无交集数组、有重复的数组。这些边界测一遍基本就能确认代码是对的。最后分享一点实际刷题心得这三道题我前后刷了不止一遍印象最深的是 438 的窗口更新顺序问题。有一版代码我写反了左右字符的更新顺序小样例全部通过到了长字符串样例就错排查了十分钟才发现是逻辑上虽然窗口长度不变但中间状态会影响 differ 的计数。所以后来我养成了一个习惯滑动窗口的代码每次只改窗口“进入”和“离开”两个点写完先自己在纸上推一遍三个字符的例子再提交。另外代码随想录的 Day09 这三题很适合放在一起做三刷。第一刷用 Set/Map 的天然写法第二刷用双指针写一遍 349 和 350第三刷把 438 的 differ 优化版本默写出来。三轮下来哈希表的基本功就扎实了。后面遇到再复杂的字符串题目你会发现底层逻辑还是这三道题里练出来的那几板斧。