如果你在找力扣刷题攻略那力扣 438 绝对是绕不开的一道题。找到字符串中所有字母异位词这题表面上是“哈希表滑动窗口”的入门题实际上却承载着字符串类题目里最重要的一个思维转变把“是否互为排列”这种看起来需要全排列比较的问题翻译成“频次是否相等”的统计问题。我见过太多候选人能把 438 的代码默写出来但被问一句“为什么窗口长度超过 p 时才收缩”就当场卡壳。这篇就用一道题的量把滑动窗口的原理、两种写法的选择、刷题时的延伸路径一次讲透。1. 先搞懂 438 在考什么异位词问题背后的“窗口思维”1.1 题目到底在说什么题目描述很简单给你两个字符串s和p找到s中所有p的字母异位词的子串返回这些子串的起始索引。字母异位词指字母相同但排列不同的字符串。比如p abc那么abc、bca、cab都是p的异位词。举个例子s cbaebabacdp abc答案就是[0, 6]因为s[0..2] cba是abc的一个排列s[6..8] bac也是。这里最关键的一个洞察是如果两个字符串长度相同并且每个字母出现的次数都相同那它们就互为字母异位词。换句话说我们根本不需要把p的所有排列罗列出来去逐个匹配只需要检查“某个子串的字母频次表”和“p 的字母频次表”是否完全一致。从这道题开始很多字符串匹配问题都走上了同一条路不再关心字符的具体顺序而是关心字符的数量关系。这种抽象能力是刷题时最容易培养、也最容易被忽略的核心能力。1.2 暴力解法的复杂度噩梦新手第一次看到这个题最容易想到的解法是枚举s中所有长度为len(p)的子串对每个子串做一次排序然后跟排好序的p比较。假设n s.length()m p.length()枚举的子串数量是n - m 1个每个子串排序要O(m log m)整体复杂度就是O(n * m log m)。一旦s和p的长度来到10^5量级这个复杂度基本就是运行超时。哪怕每个子串只做一次频次统计也要O(n * m)仍然不够优秀。滑动窗口能解决这个问题核心在于一个观察窗口从左往右滑动的过程中相邻两个窗口之间有m-1个字符是重复的。也就是说与其每次重新统计窗口内所有字符不如维护一个“增量”的频次数组——每次移动时左侧出一个字符右侧进一个字符频次数组只需要修改两处。这样一来每次维护窗口状态的时间是O(1)整体复杂度降到O(n)。2. 滑动窗口的核心逻辑从“重新排序”到“计数对齐”2.1 窗口如何伸缩滑动窗口的模板其实很固定。拿 438 来说我们需要两个指针left和right两者维护的区间[left, right)就是当前的“窗口”。我们用need[26]记录p中每个字符出现的次数用win[26]记录当前窗口中每个字符出现的次数。right每向右移动一位就把新进来的字符在win中加一。当窗口长度等于m时我们比较need和win是否相等如果相等说明窗口对应的子串就是p的一个异位词。关键问题来了窗口什么时候收缩在固定窗口长度的问题里答案很简单——窗口长度一旦超过m就必须让left收缩。因为p的异位词长度一定是m窗口长度不可能比m还长否则即使字符频次匹配长度也不对。具体到代码上有两种常见写法。一种是以right为主循环变量每次先扩展right当窗口长度大于m时收缩左边界然后判断。另一种是先手动初始化一个长度为m的窗口然后每次左右指针各移动一位像一条毛毛虫一样往前爬。我个人更喜欢后一种逻辑更简洁也更容易延伸到其他滑动窗口问题里。2.2 为什么可以用数组而不是哈希表因为题目限定只有小写字母字符集大小是固定的26所以直接用int need[26]和int win[26]就足够了。字符c对应的下标就是c - a。这里有个很多人忽略的点比较两个频次数组是否相等用vectorint可以直接写need win但如果是 C 语言风格的原生数组是不能直接用比较内容的。所以我在 C 里一般用vectorint而不是int[]目的就是让代码更干净少写一个std::equal。在时间复杂度上每次比较频次数组需要遍历 26 个位置是O(26)可以看成常数。整体复杂度仍然是O(n)空间复杂度O(1)。2.3 一个关键细节先移动 right 再判断还是先构造初始窗口很多刷题攻略里的代码版本不一样但本质思路是一样的。区别在于你是从空窗口开始“边移动边判断”还是先搭好一个初始窗口再“滑动判断”。先搭窗口的写法是这样的for (int i 0; i m; i) { win[s[i] - a]; } if (need win) ans.push_back(0);然后主循环从i m开始for (int i m; i n; i) { win[s[i] - a]; win[s[i - m] - a]--; if (need win) ans.push_back(i - m 1); }这种写法里i既表示新进入窗口的字符也通过i - m确定离开窗口的字符非常直观。窗口[i-m1, i]的长度始终是m。另一种写法则从空窗口开始每一步先扩展右边界再判断是否需要收缩左边界最后判断是否合法。两种写法都能 AC但面试时建议选更自然、不容易出错的那一种。3. 两种主流的实现方案与对比3.1 双频次数组法直白适合面试快速讲解第一种方案就是上面展示的维护need和win两个频次数组每次窗口滑动后直接比较两者是否相等。代码很短核心就三件事用need记录p的频次。用win记录当前窗口的频次。每次窗口合法时比较两个数组是否相等。在面试场景里这种写法最大的优点是容易解释“我们不需要真正比较排列只需要比较频次”。面试官也能一眼看懂你在做什么不容易产生误解。缺点是每次比较要检查 26 个字符。虽然常数很小但如果你想让代码更“高级”一点就可以考虑第二种方案。3.2 单哈希加匹配次数优化更优雅适合追求性能第二种方案被称为“match 计数法”。核心逻辑是我们不需要每次都完整比较win和need而是维护一个变量matched表示“当前窗口中有多少种字符其数量与p完全一致”。当matched等于p中不同字符的种类数时说明窗口里的所有字符频次都与p对齐窗口就是合法解。具体实现时有个细节如果某个字符在p中根本没出现即need[c] 0这个字符不应该算进“需要匹配的种类数”里。所以要先遍历need统计出p中到底包含多少种字符这个值记为totalMatch。每次窗口变化时更新规则如下新进入窗口的字符c其频次加一。如果加完后win[c] need[c]说明这个字符刚好对齐了matched加一。离开窗口的字符d在移除之前先判断如果移除前win[d] need[d]说明当前这个字符恰好处于“对齐”状态移除后会破坏对齐所以matched减一。然后再让win[d]减一。这里最容易写错的地方是很多人先减频次再判断结果判断条件全乱套。正确的顺序是“先判断是否破坏对齐再修改频次”这个细节非常关键。带有matched优化的代码长这样class Solution { public: vectorint findAnagrams(string s, string p) { vectorint ans; int n s.size(), m p.size(); if (n m) return ans; vectorint need(26, 0), win(26, 0); for (char c : p) need[c - a]; int totalMatch 0; for (int i 0; i 26; i) { if (need[i] 0) totalMatch; } int matched 0; for (int i 0; i n; i) { int c s[i] - a; win[c]; if (win[c] need[c]) matched; if (i m) { int d s[i - m] - a; if (win[d] need[d]) matched--; win[d]--; } if (matched totalMatch) { ans.push_back(i - m 1); } } return ans; } };这段代码的性能比双数组比较更好因为它把每轮O(26)的比较优化成了O(1)的变量更新。在面试里写出这种版本通常能给面试官留下更深刻的印象因为这说明你不是在背模板而是真正理解了状态之间的转换关系。3.3 复杂度对比与选型建议方案时间复杂度空间复杂度适用场景双频次数组比较O(n * 26)实际可视为 O(n)O(1)面试快速作答、思维讲解match 计数优化O(n)O(1)追求最优性能、字符集较大哈希表统计O(n)O(k)k 为字符种类字符集不固定或涉及 Unicode如果只是刷题双频次数组法已经足够通过所有测试用例。但如果你想在滑动窗口这个专题里扎得更深match 计数法值得掌握因为它在很多“最小覆盖子串”类问题里都派得上用场。4. 刷这道题我踩过的坑从超时到边界漏判4.1 初始化的坑438 这道题第一眼看起来简单但真正提交时反而容易在边界条件上翻车。最常见的错误就是忘记判断s.length() p.length()。如果s比p短那根本不可能存在异位词子串直接返回空数组。这个特判不写代码后面必然越界访问轻则报错重则答案全错。还有一个初始化细节就是第一个窗口怎么处理。如果你用的是“先搭初始窗口再滑动”的写法别忘了在进入主循环前先判断一次初始窗口是否合法。否则你会漏掉从下标 0 开始的答案。4.2 索引计算的边界条件当找到一个合法窗口时窗口的起始位置是i - m 1而不是i也不是i - m。这个索引计算很多人推不明白我建议直接用具体例子代入当i m时窗口覆盖的是s[0..i-1]其实i - m 1 1就对应窗口内部最左侧的索引。如果s长度刚好等于p的长度那么整个s就是唯一一个需要判断的子串。这种情况下主循环不会执行但初始窗口的判断已经承担了全部工作所以答案要么是[0]要么是空。重复字符的情况也要注意。比如p aa那么窗口中必须有且仅有两个a才能算合法。频次数组天然能处理这种情况need[a] 2窗口里只有一个a就不匹配三个a也不匹配。4.3 语言层面的细节坑不同编程语言在处理字符到数组下标转换时写法不一样。C 里是s[i] - aPython 里是ord(s[i]) - ord(a)Java 里是s.charAt(i) - a。这些都是很常规的操作但我在教新手时发现很多人写错是因为在char和int的隐式转换上栽了跟头。另外C 里vectorint可以用直接比较但是原生数组不能。如果想用原生数组就要写std::equal(begin(need), end(need), begin(win))有点啰嗦。所以在可以用vector的地方我建议直接用vector省事又安全。4.4 一次真实的排查经历我印象很深的一次是我最开始写 match 版本时的经历。当时我把totalMatch初始化为 0结果窗口怎么动matched都永远不会等于totalMatch因为matched加来加去最多到某个值但totalMatch一直是 0最后发现我把“不同字符种类数”和“出现次数”搞混了。那次排查花了我快半小时。一开始我在循环里打印win和need数组发现单个字符的频次明明是对的但整体结果就是不对。后来我打印了totalMatch和matched才意识到totalMatch根本没有被正确初始化——我直接漏掉了一个遍历need数组统计种类的循环。从那以后我养成了一个习惯如果 match 版本怎么调都不对先检查totalMatch的初始化和matched的更新顺序不要一上来就怀疑滑动窗口本身的逻辑。5. 由 438 延伸出的经典变体题刷题路上的“举一反三”5.1 最小覆盖子串LeetCode 76438 练熟之后我强烈建议立刻去做 76 题“最小覆盖子串”。这两道题之间的进阶关系非常清楚。438 要求窗口长度固定等于p.length()而 76 要求窗口长度不固定只要窗口内所有目标字符的频次都达到要求即可并且要找到最短的窗口。区别在于收缩条件438 是“窗口长度超过 m 就收缩”76 是“窗口已经覆盖所有目标字符时不断尝试收缩以找到更小的窗口”。从 438 到 76是滑动窗口从“固定大小”走向“可变大小”的关键一步。如果你能独立把 76 做出来说明你已经真正理解了滑动窗口的伸缩机制。5.2 无重复字符的最长子串LeetCode 3与字符串的排列LeetCode 567LeetCode 3 题“无重复字符的最长子串”同样是滑动窗口但它的窗口合法性判断是“窗口内没有重复字符”。当你发现某个字符计数超过 1 时就收缩左边界直到该字符恢复唯一。LeetCode 567 题“字符串的排列”则是 438 的“近亲”它只要求判断s2是否包含s1的某个排列返回布尔值。其实只要把 438 的代码稍微改一下找到一个合法窗口就返回true找不到就返回false。刷完 438 再做 567你会觉得题目简直在送分。5.3 如何做横向总结刷题时要学会把“一道题”变成“一类题”。我自己常用一个表格把相似题归类题型窗口长度合法性判断代表题目固定窗口找全部合法子串固定频次完全相等438、567可变窗口求最小长度动态覆盖所有目标字符76、209可变窗口求最大长度动态满足某个限制条件3、159、340做横向总结最大的价值不是让你记住每道题的代码而是让你在做新题时能快速识别出“这题到底属于哪一类”然后套用对应的窗口伸缩策略。6. 针对刷题新手的节奏建议什么阶段适合刷 438 这类题6.1 刷题顺序安排如果你是刚开始刷题不久我的建议是先完成数组、字符串、哈希表这三个基础专题再进入滑动窗口。438 这道题恰好把字符串、哈希表和滑动窗口三者结合在了一起难度适中非常适合作为滑动窗口专题的开篇。具体顺序可以是先做 567 题热身再做 438 题巩固最后挑战 76 题进阶。如果你连“两数之和”都还没写过建议先不要碰 438毕竟哈希表和数组下标的概念还没有建立起来直接上滑动窗口容易挫败感太强。6.2 一道题刷几遍才够我个人经验是一道经典题至少刷三遍。第一遍理解题解思路能自己写出 AC 代码就算过关。第二遍隔两天不看题解限时 20 分钟独立完成并且尝试写出两种解法双频次数组法和 match 计数法。第三遍再过一周只看着题目在草稿纸上画出窗口滑动过程然后把代码默写出来。只有到了第三遍你才算是真正把这道题内化成了自己的东西。很多人刷题只刷第一遍看完题解感觉自己会了结果面试遇到原题还是写不出来就是因为少了后面这两轮“强制回忆”的训练。6.3 如何写一份有用的刷题笔记很多人的刷题笔记就是抄一遍题解代码几个礼拜后回看完全不记得当时为什么要这么写。真正的总结不是抄题解而是用自己的话把这四件事写清楚一句话题目输入是什么输出是什么。核心思想这题的关键洞察是什么比如 438 的“频次相等代替全排列比较”。易错点你实际写错过的边界条件或索引细节。复杂度分析时间复杂度和空间复杂度分别是多少。做完这些你还要把代码提炼成自己的模板。438 的模板可以直接用在 567 上只需要把返回值从vectorint改成bool。这种“改两行代码就能解决新题”的体验才是刷题带来成就感最真实的来源。最后再分享一个小技巧做完 438 之后可以顺手把 76 题的题解也读一遍看看别人是如何在同一个框架下调整窗口收缩条件的。很多时候你在 438 里养成的“固定窗口”思维反而会成为理解可变窗口的障碍提前看到两者之间的差别能让你在后面刷题时少走不少弯路。