LeetCode 438. 找到字符串中所有字母异位词这题我在Hot100里至少刷过三轮每次都会有新的理解角度。第一轮是硬做暴力排序子串后直接比较AC虽然能AC但慢得离谱第二轮学会滑动窗口加计数数组总算是踩到了点子上第三轮把diff变量彻底吃透之后再看同类题基本就是一路平推。很多朋友卡在这题卡住的点往往不是“滑动窗口”这个名词而是窗口滑动时两个计数器到底怎么同步以及到底什么时候才应该把下标记录进结果。这篇文章就把这两件事一次讲透顺便把我踩过的一些坑也一并列出来。1. 题目到底在考什么 —— 拆开“字母异位词”这层壳1.1 看清问题定义和示例题目给得相当直白给定两个字符串s和p要求在s中找到所有p的字母异位词的子串返回这些子串的起始索引。示例1里s cbaebabacd、p abc输出[0, 6]因为s[0:3]cba是abc的一种排列s[6:9]bac同样是示例2s abab、p ab输出[0, 1, 2]三个长度2的子串ab、ba、ab都满足条件。这里先把“字母异位词anagram”这件事钉死两个字符串包含的字符种类完全相同、每种字符的数量也完全相同只是排列顺序不同。换句话说比较异位词不关心顺序只关心“字符的多重集合”是否相等。所以438要我们做的事情本质上不是“匹配字符串”而是“比较两个长度相等的子串的字符频次是否一致”。这个认知非常关键。一旦意识到题目考的是频次思路就会很自然地滑向“计数数组”而不是一上来就想着排序、反转、哈希字符串那一套。很多刷题教程喜欢直接甩滑动窗口的模板但如果你没想清楚为什么是“频次相等”模板背得再熟换个壳也会认不出来。1.2 为什么这题值得常驻Hot100438在面试里出现频率极高不是因为它难恰恰是因为它处在“最合适的难度”上。它同时考察了三样东西一是滑动窗口的基本功二是对字符集大小的敏感度小写字母只有26个可以直接用定长数组做频率表三是对时间复杂度演进的判断力。从暴力到哈希再到diff优化438有一条非常清晰的优化链每走一步都能看到上一版的瓶颈在哪里为什么需要下一版。这种“有明显优化梯度”的题目其实不多大多数题要么一步到位要么怎么优化都隔靴搔痒。438特别适合用来练“分析复杂度 - 定位浪费 - 设计增量更新”的完整思维链路这也是我推荐所有刷Hot100的朋友把它排在靠前位置的原因。另外由438延伸出去的变形太多了。567. 字符串的排列是它的存在性版本76. 最小覆盖子串是它从不固定窗口到固定窗口的进阶版本30. 串联所有单词的子串则是把字符换成单词后的再升级。把438吃透等于同时给好几道题打了底子性价比很高。1.3 暴力法的问题重复劳动太严重先看一眼最朴素的解法枚举每个可能的起点i取子串s[i:im]把子串和p分别排序后比较是否相等。这里m len(p)、n len(s)排序一个长度为m的子串代价是O(m log m)一共有n-m1个起点总复杂度约等于O((n-m1) * m log m)。这个复杂度在n和m都达到3*10^4的约束下完全不可接受LeetCode上大概率直接超时。更重要的是暴力法浪费在哪里一眼就能看出来相邻两个子串之间其实有m-1个字符是重叠的但我每次都在重复排序这些重叠部分等于反复计算了大量相同的信息。滑动窗口的优化点正是从这里切入的让窗口每次只平移一个位置新窗口与旧窗口相比只是“右边多了一个字符、左边少了一个字符”其余m-1个字符完全没变。那有没有办法只更新这两个字符的计数而不是重新统计整个窗口有这就是下一节要展开的核心。2. 解法演进定长滑动窗口 频率计数2.1 从“排序比较”换成“频率比较”既然判断异位词不关心字符顺序那就不要用排序这种“保留顺序”的操作直接统计频次把p转换成一个长度为26的计数数组targettarget[i]表示字符i在p中出现的次数对于s中当前窗口的子串也构造一个同样的计数数组window。当target window时当前窗口就是一个合法异位词。这里我有一个常年坚持的小习惯题目明确说明只包含小写字母时一律用定长数组不用哈希表。26个元素的数组读写都是O(1)并且没有任何哈希碰撞、扩容的隐形成本在C和Java里写起来也顺手cnt[c - a]比map[c]优雅得多。只有当字符集不确定或者特别大比如全量Unicode时才考虑用HashMap或 Python 的Counter。这个习惯在写高频题时可以帮你省掉很多不必要的常数开销。2.2 定长窗口的推进逻辑只改两个位置窗口大小固定为m len(p)。处理过程分三步先初始化把s前m个字符填进窗口然后判断一次接着开始滑动每次右边界读入一个新字符左边界移除一个旧字符再判断一次。因为窗口尺寸恒定每个字符在整个过程中只会被“加入”一次、“移除”一次整体操作次数严格与n成正比。这里可以找一个接地气的类比一条传送带匀速前进你手里有个固定尺寸的检测框框跟着传送带一起走每走一格右边进来一个产品、左边出去一个产品。你要判断的是框内产品的“构成”是否和标准包一致而不是每次把框里的东西全倒出来重新装一遍。滑动窗口的精髓就在这用上一次的状态做增量更新而不是从零开始重建。很多人第一次写的时候会犯一个低级错误在循环里重新对窗口内所有字符做一次统计。那就退回了暴力解完全没有利用滑动窗口“增量”的优势。正确姿势是把读入和移除分开写每次循环只操作两个字符。2.3 每步全量比较最容易理解的第一版先给出一个思路最清晰的实现用两个数组每步移动后直接比较两个数组是否相等。这个版本的复杂度是O(26n)虽然带个常数26但对于这题的约束完全能过而且代码极短面试时先写这版再优化是很稳妥的节奏。class Solution: def findAnagrams(self, s: str, p: str) - List[int]: n, m len(s), len(p) if n m: return [] target [0] * 26 window [0] * 26 for ch in p: target[ord(ch) - ord(a)] 1 res [] for i in range(n): # 右边界字符进入窗口 window[ord(s[i]) - ord(a)] 1 # 窗口长度超过 m 时左边界字符离开窗口 if i m: window[ord(s[i - m]) - ord(a)] - 1 # 窗口完整时才判断 if i m - 1 and window target: res.append(i - m 1) return res这段代码里的两个if值得反复咀嚼。i m控制的是“窗口还没满之前不需要移除字符”i m - 1控制的是“窗口长度刚好等于m时才开始记录答案”。这两个条件的含义不同千万别合并成一个也别漏掉前者。漏掉前者会导致负计数漏掉后者会把长度不够m的子串误判为合法结果。2.4 引入 diff 变量把每次全量比较变成实时维护既然每次只是“进一个出一”那window target的比较结果其实也不需要用26个位置逐项比可以维护一个变量直接记住“当前有多少个字符的计数和目标是不同的”。这个变量的名字业界习惯叫diff或need在438这种定长窗口题里diff的初始值等于target中非零项的个数或者target - window的差值非零项个数。每次滑动时被操作的字符只有两个新进的右端字符和离开的左端字符。对每个被操作的字符更新diff的规则可以提炼成两句话操作之前这个位置的计数等于0说明原来是“平衡”状态操作之后它必然变成非零那么diff 1操作之前这个位置的计数不等于0操作之后恰好归零说明从“不平衡”变成了“平衡”那么diff - 1。顺序上必须“先判断旧状态再执行加减最后判断新状态”这个顺序不能乱。我第一次写diff优化时就是把加计数和更新diff的顺序搞反了结果每次答案都差一位排查了半天。下面给出用单数组cnt表示“窗口计数减目标计数”的写法cnt全为0时diff 0也就是窗口合法。class Solution: def findAnagrams(self, s: str, p: str) - List[int]: n, m len(s), len(p) if n m: return [] cnt [0] * 26 # 目标中每个字符记为 -1等价于窗口的计数需要抵消掉这些 for ch in p: cnt[ord(ch) - ord(a)] - 1 # 初始不平衡的字符种类数 diff sum(1 for v in cnt if v ! 0) res [] for i in range(n): # 右端进入 idx ord(s[i]) - ord(a) if cnt[idx] 0: diff 1 cnt[idx] 1 if cnt[idx] 0: diff - 1 # 左端离开 if i m: idx ord(s[i - m]) - ord(a) if cnt[idx] 0: diff 1 cnt[idx] - 1 if cnt[idx] 0: diff - 1 # 窗口完整且所有字符都平衡 if i m - 1 and diff 0: res.append(i - m 1) return res这版代码里cnt的语义是“当前窗口相对目标的差值”。正值表示当前窗口里该字符比p多负值表示比p少。所以右端进入一个字符要做1左端离开一个字符要做-1数学方向正好是反的。理解了这个符号方向读代码就不会晕了。3. 代码落地多语言实现与关键细节3.1 Python 版本一双数组全量比较面试保底写法双数组版本适合作为面试时的第一反应它没有diff变量那些“先判断再操作”的心智负担代码逻辑最直白。性能方面window target在 CPython 里是两个列表的逐元素比较最多26次整数比较常数很小实际运行时间也就在几十毫秒级别完全可以作为最终答案提交。class Solution: def findAnagrams(self, s: str, p: str) - List[int]: n, m len(s), len(p) if n m: return [] target [0] * 26 window [0] * 26 for ch in p: target[ord(ch) - 97] 1 res [] for i in range(n): window[ord(s[i]) - 97] 1 if i m: window[ord(s[i - m]) - 97] - 1 if i m - 1 and window target: res.append(i - m 1) return res这里我用了ord(ch) - 97代替ord(ch) - ord(a)效果一样纯属个人习惯。面试时写ord(a)语义更清楚直接写97也不会有问题但不太推荐万一字符集换成了大写字母97这个魔法数字就得推倒重来。3.2 Python 版本二diff 优化进阶必学写法diff版本在面试里属于加分项。它的判断从O(26)降到了O(1)并且展示了你对状态维护的理解深度。我建议在把双数组版本写顺之后再花一晚上把这版逻辑彻底搞明白后面做76. 最小覆盖子串时会有极大帮助。diff版本里最常见的困惑点是为什么进字符和出字符都要写一遍相同的“三连”因为它们操作的对象都是同一个数组只是方向相反进来加计数出去减计数而且每个字符在离开窗口的那一刻同样可能从平衡变不平衡、从不平衡变平衡。你可以把这段逻辑封装成一个函数但LeetCode题解里通常直接平铺因为内联代码更省时间。class Solution: def findAnagrams(self, s: str, p: str) - List[int]: n, m len(s), len(p) if n m: return [] cnt [0] * 26 for ch in p: cnt[ord(ch) - 97] - 1 diff 0 for v in cnt: if v ! 0: diff 1 res [] for i in range(n): idx ord(s[i]) - 97 if cnt[idx] 0: diff 1 cnt[idx] 1 if cnt[idx] 0: diff - 1 if i m: idx ord(s[i - m]) - 97 if cnt[idx] 0: diff 1 cnt[idx] - 1 if cnt[idx] 0: diff - 1 if i m - 1 and diff 0: res.append(i - m 1) return res从时间复杂度看每个字符只会被cnt增删各一次所以总复杂度严格O(n)空间复杂度O(1)固定26长度的数组。这题的O(n)是可以稳定达到的不存在比它更优的复杂度了。3.3 C 版本对比同样的逻辑不同的手感C 写法思路完全一致只是把 Python 的ord换成c - a并且用vectorint存计数。class Solution { public: vectorint findAnagrams(string s, string p) { vectorint res; int n s.size(), m p.size(); if (n m) return res; vectorint cnt(26, 0); for (char c : p) cnt[c - a]--; int diff 0; for (int x : cnt) if (x ! 0) diff; for (int i 0; i n; i) { int idx s[i] - a; if (cnt[idx] 0) diff; cnt[idx]; if (cnt[idx] 0) diff--; if (i m) { idx s[i - m] - a; if (cnt[idx] 0) diff; cnt[idx]--; if (cnt[idx] 0) diff--; } if (i m - 1 diff 0) res.push_back(i - m 1); } return res; } };C 版本有个额外好处vectorint的比较和赋值都是线性操作但代码里全程没有复制整个数组只是单个元素的读写cache 友好度很高。用vectorint而不是arrayint, 26也完全可以LeetCode 环境两者相差无几。3.4 初始化和判断时机的三个细节第一cnt初始化为-p的计数这一步也可以用两个数组写好再求diff但单数组写法省了一个target少了一整个数组的维护量。代价是符号方向需要自己理清楚写错了很容易出负数。第二diff的初始值必须是在窗口还没开始滑动时就计算好的“不平衡种类数”不是0也不是m。如果p包含a两个、b一个那cnt里a位置是-2、b位置是-1其余位置是0diff初始为2。这个初始值的正确性直接影响后续所有判断值得单独写一行注释说明。第三为什么答案记录条件必须是i m - 1因为当i等于m-1时窗口正好覆盖了s[0:m]长度首次达到m。在这之前窗口是不完整的即使diff意外为0也没有意义。设置了这个条件之后循环结束后不需要再单独补一次最后的窗口判断所有情况都在循环里覆盖完了。4. 高频错误与排查实战4.1 左右指针的索引错位我见过最普遍的写错方式是把“左端离开的字符”写成了s[i - m 1]或者s[i - m - 1]。窗口每次移动一格当前遍历到的下标是i新进入的是s[i]而离开的必然是最早进入窗口的那个字符也就是s[i - m]。这个偏移量不能靠感觉最好在纸上画一下索引轴。排查技巧也很简单把代码里的left和right下标打印出来跑sabcabc、pabc看看第一轮滑动时离开的字符到底是什么。如果离开的是b而不是a说明索引偏移算错了。这种错用眼睛盯半天很难盯出来打印日志一下就能定位。4.2 计数数组出现负数是不是bugdiff版本的cnt允许出现负数这一点很多人不适应。想想cnt表示的是“窗口计数减目标计数”当窗口里某种字符比p少时对应位置当然是负数。比如窗口是ab、目标是abcc的位置就是-1完全正常。但有个前提如果同一位置出现绝对值大于目标总数的负数比如目标里a只有1个cnt[a]却变成-3那大概率是左端移除的逻辑没写对或者你人为减多了。正常的滑动过程中每个字符在窗口里出现的次数不会超过p中该字符的总数加1因为窗口大小就是len(p)所以绝对值不会失控。4.3 Python Counter 版本的价值与坑用Counter写438是非常“Pythonic”的代码很短但有两个坑值得注意。第一个坑是window target时如果window里某个键的计数恰好减到0旧版本Python3.9及以前的Counter比较会把Counter({a: 1, b: 0})和Counter({a: 1})当作不相等导致漏判Python 3.10之后官方修改了Counter.__eq__会忽略零值和负值计数。为了兼容很多老题解里写if window[left] 0: del window[left]这个del就是为此服务的。第二个坑是del之后再往同一个键加计数会重新创建键逻辑上没问题但如果你在循环里频繁del又1代码的可读性会下降。我的建议是面试时除非面试官明确要求用Counter否则一律用定长数组。数组版本没有删除键的烦恼也更容易向面试官讲清楚底层原理。4.4 边界条件速查表438的边界条件不算复杂但很容易在细节上翻车。我把常见边界情况整理成了一个表刷题时可以直接对照场景期望结果易错点n m直接返回空数组提前特判避免后续索引越界n m且 s 是 p 的异位词[0]初始窗口判断不能漏n m且 s 不是 p 的异位词[]不能在循环外多写一次判断s和p完全无重叠字符[]diff永远不会归零正常p中相同字符出现多次如aabb按频次严格匹配不能只判断Set相等要比较频次字符串长度很大窗口滑动次数多全量通过检查是否误用O(m)的子串拷贝最后一行特别重要。有些解法为了省事直接写s[i:im]之后再比较这在Python里每一次切片都会产生一个新字符串复杂度退化成O(n*m)数据一大就超时。凡是需要“取长度为m的子串”的操作都应该用滑动窗口而不是字符串切片。4.5 一个越想越值的调试案例我第一次写diff版本时输出的结果比标准答案整体偏左一位。排查了半天发现是记录答案时写成了res.append(i)而正确的起点应该是i - m 1。为什么错因为当我遍历到i时窗口的起点是i - m 1而不是i。只有当m1时两者才相等但m1只是特例不能拿特例当通解。后来每次写完滑窗题我都会用m1和mn两组特殊数据自测一遍m1能暴露索引偏移问题mn能暴露初始窗口判断是否遗漏。这两组数据的成本几乎为零收益却极高。5. 一题通一类把438沉淀成滑窗解题模板5.1 定长滑窗的通用模板做完438后我建议把它抽象成定长滑窗的模板以后遇到“找字符串中所有满足某性质的定长子串”这类题直接套骨架子。模板的核心四步是预处理目标信息建计数表初始化窗口计算初始差异循环推进窗口右进、左出、更新状态每次窗口完整时根据状态决定是否记录答案。def fixed_window_template(s, p, check): n, m len(s), len(p) if n m: return [] state init_state(p) # 根据需要初始化状态 diff init_diff(state) # 初始差异 res [] for i in range(n): update_state(state, s[i], 1) # 右端进 if i m: update_state(state, s[i - m], -1) # 左端出 if i m - 1 and check(diff): res.append(i - m 1) # 窗口完整时判断 return res模板里的update_state和check都是占位概念具体到438update_state就是那套“先判断旧状态、再改计数、最后更新diff”的三连。用模板不是为了少写代码而是为了强迫自己把滑动窗口的五个要素左右边界、状态结构、状态更新方式、答案记录条件、初始状态在动笔之前想清楚。5.2 同类型题目对照438的好兄弟有不少我按关联度排了个序567. 字符串的排列几乎一样的思路只不过不需要记录所有起点一旦发现diff 0直接return True。代码改3行就过。76. 最小覆盖子串不定长滑窗维护的不再是“定长窗口”而是“覆盖目标的最短子串”状态更新里多了一个控制左指针收缩的条件是438思想的重要延伸。49. 字母异位词分组把单词排序或转成“频次向量”后作为key做哈希分组核心仍然是频次比较。242. 有效的字母异位词没有滑动纯计数是438的退化版。建议一次把567和438连着做等于把“找到所有起点”和“判断是否存在”对比着练能加深对窗口“在哪一步记录答案”的理解。5.3 三个刷题建议第一个建议做438这类题第一遍一定不要直接看题解。先自己在纸上模拟scbaebabacd的整个滑窗过程把每次右进左出后的计数器状态写出来亲手跑通三个完整窗口之后再写代码。这样写出来的代码不是背出来的是理解出来的。第二个建议准备一个自测集。我刷字符串滑窗题会固定用三组数据测m1、mn、s和p完全无交集。这三组覆盖了最大多数边界错误做多了你会发现很多提交失败在用例30才暴露的问题这三组数据在本地就能提前拦住。第三个建议把复杂度分析讲完整。面试官问这题时常常会追问“为什么不能用HashMap”你如果能说出定长数组在哈希碰撞、扩容、缓存局部性上的优势再对比一下字符集变大之后要切回HashMap的权衡这道题就稳了。我个人在实际中体会最深的一点是438的diff版本看起来只是常数优化但那个“先判断旧状态、再更新、最后判断新状态”的顺序是几乎所有进阶滑窗题的核心节奏。把它练成肌肉记忆再去啃76题和30题你会发现自己的状态更新逻辑清晰得多。另外分享一个小技巧每写完一版滑窗都试着用语言把窗口移动的过程讲给身边的人听讲得明白才算真会了。这题后续想再进一步可以尝试把p换成单词数组的30. 串联所有单词的子串那才是真正考验你模板复用能力的一道题。