如果你在 LeetCode 上刷过字符串类题目多半会撞见第 438 题找到字符串中所有字母异位词。这题表面看是“给你一个字符串 s 和一个字符串 p找出 s 中所有 p 的字母异位词子串”但真上手写的时候很多人第一反应都是切片排序、Counter 硬比结果一提交就被超时打脸。它的核心解法是滑动窗口进阶一点可以用双指针但真正拉开差距的是你有没有把“计数相等”这四个字想透。这篇文章我会从暴力解法开始逐步拆到定长滑动窗口、双指针收缩窗口再讲清楚复杂度真相、边界条件和面试时容易被追问的点适合刚刷题的小白也适合想把这题讲明白再去面试的人。1. 题目读透异位词的本质是“计数相等”不是“顺序相等”1.1 从题目描述到可执行条件先看题目“字母异位词”指的是字母相同、排列不同的字符串。比如 p abc那么 abc、bca、cab、acb、bac、cba 都是它的异位词。题目要求你返回 s 中所有这样的子串的起始下标。朴素理解是“乱序匹配”但乱序怎么判断排序当然可以可如果每次都排序等于把一个连续子串恢复成有序序列再去比较代价很高。真正该做的是把判断条件翻译成数学语言两个字符串互为字母异位词当且仅当它们长度相同且每个字符出现的次数完全相同。也就是说这道题由“字符串匹配”变成“频次匹配”。一旦想通这一点题目就简单了维护一个长度为 len(p) 的窗口窗口内每个字符的计数与 p 的计数一致时窗口起点就是一个答案。1.2 排序法为什么只能当暴力解很多人的第一版代码长这样从 s 的每个位置 i 开始截取长度为 m 的子串排序后和排序后的 p 比较。这个方案逻辑上完全正确但复杂度是 O(N * M log M)N 是 s 的长度M 是 p 的长度。当 s 很长而 p 也不算短时这个复杂度在 LeetCode 的大数据用例下几乎肯定超时。我见过不少人卡在这一步然后怀疑是不是 Python 太慢其实不是语言问题是算法本身就不该这么干。你想想相邻两个子串之间只差了头尾两个字符中间部分完全没变却要重新排序等于把前面已经算过的信息全扔了这显然是浪费。所以排序法我只建议用来干什么用来写一个“逻辑绝对正确但速度不达标”的基准版本拿来和优化后的滑动窗口版本对拍验证边界输出一致。日常刷题时我不会把它当正式解法。1.3 动笔前先约定字符集还有一个很多初学者忽略的细节题目通常会说明 s 和 p 仅包含小写字母。这意味着字符全集只有 26 个用固定数组做计数器是最好的选择。但如果在面试中面试官把条件改成“字符集不确定”或者“包含 Unicode 字符”固定数组就不适用了需要用哈希表。所以我的建议是写代码前先问自己一句字符集是什么如果明确是小写字母就放心用长度为 26 的数组如果不确定就写 Counter 或 defaultdict(int)可读性更好也能覆盖更广的场景。这不是小题大做面试里很多时候考察的就是这种约束识别能力。2. 定长滑动窗口固定窗口加滚动计数这是整套方案的地基2.1 窗口长度为什么必须是 len(p)这是异位词和“最小覆盖子串”之类问题最不一样的地方。p 的异位词长度不会变一定是 len(p)所以窗口长度是固定的。固定窗口意味着每次移动只需要两件事右边进来一个新字符左边出去一个旧字符然后检查当前窗口的计数是否和 p 的计数相等。为什么这样就能覆盖所有答案因为所有可能的异位词子串如果存在它的长度必然是 m它必然从某个下标 start 开始到 startm-1 结束。当窗口从 start-1 移动到 start 时它就已经被检查过了。窗口每步只滑动一个位置所有连续长度为 m 的子串都会被遍历到一个不漏。有人可能会问为什么不直接枚举起点枚举起点本身没错但每次从零开始统计长度 m 的窗口是 O(m)整体就是 O(N*m)。滑动窗口的价值在于复用窗口移动一格你只需要把新字符的计数加一把旧字符的计数减一其他 25 个字母的计数完全不用动。这就是滚动计数的意义。2.2 用数组还是 Counter数据结构的选型逻辑在小写字母的场景下我推荐用数组[0] * 26。原因很简单数组按下标访问是 O(1)更新也快比较两个长度为 26 的列表在 Python 里是直接比较底层内存块速度极快。Counter 写起来更省事尤其是在字符集不固定的场景下。但它的每次更新涉及哈希计算窗口移动 N 次就要算 N 次哈希常数会比数组大。对于这种字符集只有 26 个的题数组是最优解。不过话说回来如果你在面试现场一时紧张用 Counter 写对了也能过。面试官通常更关心你能不能把思路讲清楚而不是纠结常数级别的差异。但在 LeetCode 上刷题追求效率时数组版本是更好的答案。2.3 窗口滚动的完整代码与一次执行验证下面是我常用的定长滑动窗口版本def find_anagrams(s: str, p: str): ns, np len(s), len(p) if ns np: return [] base ord(a) p_cnt [0] * 26 win_cnt [0] * 26 for ch in p: p_cnt[ord(ch) - base] 1 for i in range(np): win_cnt[ord(s[i]) - base] 1 ans [] if win_cnt p_cnt: ans.append(0) for i in range(np, ns): # 右侧新字符进入窗口 win_cnt[ord(s[i]) - base] 1 # 左侧旧字符离开窗口 win_cnt[ord(s[i - np]) - base] - 1 if win_cnt p_cnt: ans.append(i - np 1) return ans拿题目自带例子验证一下s cbaebabacdp abc。初始窗口是 cba计数里 a、b、c 各 1与 p 一致记录下标 0。窗口右移到 ba e 也就是 bae其中 e 不在 p 里计数立刻不匹配。一路滑到 bac 时计数重新匹配记录下标 6。最后返回[0, 6]和题目要求一致。整个过程里每次比较只需要看一眼两个长度为 26 的列表是否相等完全不需要关心窗口内部字符的顺序。2.4 两个容易被忽略的性能细节第一个细节不要把win_cnt p_cnt改成自己去遍历 26 个字母逐个比较。Python 的列表比较是内建操作C 语言层面完成非常快。你手动写 for 循环反而慢还容易写错。第二个细节窗口滑动时先加右侧字符再减左侧字符顺序无所谓因为加减是同一个字母的两个不同下标。但要注意减去的必须是s[i - np]代表窗口左侧离开的那个字符千万别写成s[i]或者s[i - 1]这种笔误很隐蔽测试用例一多就容易翻车。3. 双指针解法从“定长滑动”升级到“动态收缩”3.1 双指针和滑动窗口到底是不是一回事很多文章把双指针和滑动窗口混着说其实它们不是同一个概念。滑动窗口是一种解决问题的框架双指针是实现窗口移动的两种具体方式之一。第 438 题更准确的称呼是“窗口大小固定的滑动窗口”因为它每一步窗口长度都是 m。但为什么标题里会有双指针因为还存在另一种写法不限制窗口长度而是用两个指针维护一个窗口右指针不断向右扩张左指针在字符“超额”时向右收缩最后当窗口长度等于 m 且内部字符频次符合要求时记录答案。这种写法在算法层面和定长窗口最终结果完全一致但思考路径不同也更接近 LeetCode 76 题“最小覆盖子串”的思路。面试的时候如果你能先讲固定窗口版本再补一句“这道题也可以用双指针收缩的方式实现思路可以套最小覆盖子串模板”通常能加不少印象分。3.2 用“预算”理解窗口如何伸缩双指针版本的难点在于什么时候扩什么时候缩。我把 p 的每个字符需求量看作“预算”。比如 p abc初始预算就是 a:1、b:1、c:1。右指针每读入一个字符就把对应预算减 1如果减完之后这个字符的预算仍然大于等于 0说明这个字符还在“计划内”记一个有效匹配数 matched。如果预算变成负数说明这个字符出现得比预期多属于超额字符matched 不变。左指针收缩时做相反操作把离开窗口的字符预算加 1如果加完之后这个字符的预算大于 0说明它曾经是超额吃掉的现在补回来了matched 减 1。如果加完之后预算还是小于等于 0说明这个字符离开窗口之后窗口依然处于“超额”或“刚好”的状态matched 不变。听起来有点像记账对吧其实就是记账。matched 的意思就是“当前窗口内有多少个字符量是刚好被满足的状态”。当 matched 等于 m 时说明窗口内所有要求的字符都已经出现且数量没有超标这时候如果窗口长度也恰好等于 m那这个窗口必然是合法的异位词。3.3 完整实现与代码注释def find_anagrams_two_pointer(s: str, p: str): ns, np len(s), len(p) if ns np: return [] base ord(a) need [0] * 26 for ch in p: need[ord(ch) - base] 1 ans [] left 0 matched 0 for right in range(ns): ch s[right] idx ord(ch) - base need[idx] - 1 if need[idx] 0: matched 1 while matched np: if right - left 1 np: ans.append(left) left_ch s[left] left_idx ord(left_ch) - base need[left_idx] 1 if need[left_idx] 0: matched - 1 left 1 return ans这段代码对 s ababp ab 的执行结果是[0, 1, 2]下标 0 的 ab、下标 1 的 ba、下标 2 的 ab 都是答案。你可以手动走一遍右指针扩张到第二个字符时 matched 达到 2此时窗口长度正好是 2记录下标 0随后左指针收缩预算恢复等到右指针继续走又会遇到新的 matched 等于 2 的状态于是记录下标 1 和 2。整个过程中窗口长度始终不超过 2但比定长窗口的描述更“动态”。3.4 为什么 matched 达到 len(p) 不等于立刻记录这是双指针写法里最容易想岔的地方。matched 等于 np 只能说明“窗口里已经集齐了 p 需要的那几种字符且每种都没超出预算”但窗口里可能还混着很多多余的字符。比如 s abbbacp abc某个瞬间窗口可能是 abbba里面 a、b 都有c 也出现过可窗口长度远大于 3显然不是异位词。所以 while 循环里要先检查窗口长度是否等于 np是就记录不是就继续收缩直到 matched 不再等于 np 为止。这里有个小细节收缩过程中如果左指针离开的字符并不是 p 需要的字符比如某个字母完全不在 p 里对应预算加 1 后可能从负数变 0matched 不会变循环会继续收缩。这个行为是故意的目的是把混进来的无关字符全部排出窗口。我在第一次写双指针版本时就是漏了“收缩时 matched 不一定立刻下降”这一点导致把一些长度不符的窗口也记录进去了。后来我意识到matched np只是候选条件长度相等才是最终条件。4. 多种实现方案的复杂度对比与选型建议4.1 四类方案的比较表把几种思路摆在一起看差异就很明显了方案时间复杂度空间复杂度实现难度适用场景排序截取法O(N * M log M)O(M)最低小数据量或验证逻辑定长滑窗 数组计数O(N 26)O(1)低小写字母最推荐定长滑窗 CounterO(N) 均摊O(字符集大小)低字符集不固定双指针收缩窗口O(N 字符集)O(字符集)中面试进阶可延伸到最小覆盖子串定长滑窗 diff 计数O(N)O(1)中高追求极致性能严格来说定长滑窗每次比较两个长度为 26 的数组是 O(26)所以总复杂度写作 O(26N) 更严谨。但因为 26 是常数且列表比较在 Python 内部是 C 层完成实际运行非常快所以通常直接说是 O(N)。4.2 实测印象list 比较 vs Python 循环我在本地跑过几组测试s 长度十万级、p 长度几千定长滑窗数组版大概几十毫秒完成。如果换成 Counter 版本时间会上升到一两百毫秒但依然能过。真正慢的是每次都用sorted(s[i:im])的版本十万级输入基本要跑好几秒完全不是一个量级。这里有个非常反直觉的结论定长滑窗的数组版就算每次移动都比较 26 个字母速度依然很快。原因就是列表相等判断不是 Python 循环而是底层直接比较内存块。很多初学者为了“优化”这个比较改成手动维护 diff 计数反而在 Python 循环里浪费了大量时间属于画蛇添足。4.3 diff 计数优化把每次 O(26) 的比较降下来如果非要在数组版上做优化正确姿势是维护一个 diff 变量表示当前窗口计数与 p 计数之间有多少个字母不一样。diff 为 0 时窗口就是合法异位词。def find_anagrams_with_diff(s: str, p: str): ns, np len(s), len(p) if ns np: return [] base ord(a) p_cnt [0] * 26 win_cnt [0] * 26 for ch in p: p_cnt[ord(ch) - base] 1 for i in range(np): win_cnt[ord(s[i]) - base] 1 diff sum(1 for i in range(26) if p_cnt[i] ! win_cnt[i]) ans [] if diff 0: ans.append(0) for i in range(np, ns): add_idx ord(s[i]) - base before win_cnt[add_idx] p_cnt[add_idx] win_cnt[add_idx] 1 after win_cnt[add_idx] p_cnt[add_idx] if before and not after: diff 1 elif not before and after: diff - 1 rem_idx ord(s[i - np]) - base before win_cnt[rem_idx] p_cnt[rem_idx] win_cnt[rem_idx] - 1 after win_cnt[rem_idx] p_cnt[rem_idx] if before and not after: diff 1 elif not before and after: diff - 1 if diff 0: ans.append(i - np 1) return ans这个版本的时间复杂度严格来说是 O(N)因为每次滑动只更新两个字母的 diff 状态不再扫 26 个字母。但它代码更复杂笔试时难度也更高所以我一般只在面试被追问“能不能再优化”的时候才写。5. 边界条件与检查清单这些小坑不处理必翻车5.1 长度关系的三种前置判断第一种s 比 p 短直接返回空列表。这个判断最基础也最容易忘。如果 s 的长度是 3p 的长度是 5s 里根本不可能存在长度为 5 的子串。第二种s 和 p 长度相等。此时只需要检查 s 整体是不是 p 的异位词是就返回[0]不是就返回[]。定长窗口代码天然能处理这种情况但双指针版本要注意 left 的移动不能越界。第三种p 为空字符串。LeetCode 原题一般保证非空但在工程思考时还是要问一句。如果按“空串是任何字符串的异位词”来理解答案可能是所有位置如果按业务逻辑直接返回空也合理。面试时把这个歧义主动抛出来反而显得你考虑周全。5.2 重复字符与重叠窗口怎么测字母异位词题目里p 很可能有重复字符比如 p abab。这种情况下计数数组里 a 和 b 都是 2滑动窗口比较的是“整体频次”依然能正确处理。但有个容易踩的坑是看到窗口里有 a 和 b 就觉得满足忘了数量要对上。重叠窗口也要重点测。例如 s aaaaaap aaaa正确答案是[0, 1, 2]因为从下标 0、1、2 开始各有一个长度为 4 的全 a 子串。如果用定长窗口每次比较都准如果用双指针matched 会一直保持等于 4循环收缩时会连续记录三个答案这类用例专门用来验证 while 收缩逻辑是否完整。5.3 验证用例设计手动造数据而不是靠感觉我刷题有个习惯代码写完先不急着提交先手动构造几个特殊用例跑一遍。这道题的固定测试清单大概是s cbaebabacd, p abc期望[0, 6]s abab, p ab期望[0, 1, 2]s aaaaaa, p aaaa期望[0, 1, 2]s abc, p abcd期望[]s abc, p abc期望[0]s , p 需要结合题意确认这几个用例基本覆盖了常规逻辑、重复字符、重叠窗口、长度不足、全等和空串六种情况。跑完这些再交比我靠 LeetCode 的大用例去试错效率高得多。5.4 面试追问的应对思路面试官最喜欢在 438 题后面加追问。比较常见的几个如果字符集扩大到所有 ASCII 字符怎么改答把数组长度从 26 改成 128或者直接用 Counter。如果字符集是任意 Unicode 字符呢答数组不现实用哈希表计数。如果 s 特别长p 很短内存受限怎么办答定长滑窗本身只维护一个计数器空间是常数但要注意不能一次性把 s 载入内存的场景那时可以改成流式处理边读边滑。如果要求返回所有异位词的起始下标但要保证顺序怎么办答右指针向右扫描左指针同步滑动记录的顺序天然就是从小到大的不用担心排序问题。6. 离开题目本身这套思路还能迁移到哪6.1 背下来的不是代码是“计数器窗口”骨架第 438 题值得记的不是代码本身而是这个思维链先判断问题能不能转化为“频次匹配”再确定窗口长度是固定还是动态然后选择合适的计数器结构最后处理边界。这套骨架在字符串题里出现频率极高。我习惯在笔记本里把滑动窗口的模板写成伪代码每次遇到新题先往模板里套套不进去再想变体。比如这题是“窗口长度固定”下一题可能是“窗口长度不固定、求最小满足条件的子串”模板的 matched 计数部分几乎不用改改的只是记录条件和收缩时机。6.2 同款思路直接可用的变形题LeetCode 567 题“字符串的排列”和第 438 题几乎一样只是最后只问是否存在不要求返回所有下标。用定长滑窗做最简单。LeetCode 76 题“最小覆盖子串”则是动态窗口的代表作。右指针扩张到覆盖 p 的所有字符后左指针尽量收缩找到最短的合法子串。它和 438 的双指针写法非常像但你只需要记录最短长度而不是记录所有等于 m 的窗口。LeetCode 3 题“无重复字符的最长子串”也是滑动窗口不过计数器记录的是“当前窗口内是否存在重复字符”收缩条件变成了“有重复就移动左指针直到没有重复”。同样是双指针加计数器语义完全不同。这三道题放一起刷你会对滑动窗口有更系统的认识。6.3 真实工程里的滑动窗口场景不要觉得滑动窗口只是算法题里的玩具。真实项目里最常见的例子就是日志监控统计最近一分钟内的错误次数、最近一小时内某个接口的请求量本质上都是维护一个时间窗口新事件进入旧事件离开计数器滚动更新。另一个常见场景是网络流量统计比如限制单位时间内的最大请求数。还有流式数据处理数据一条条到达没法整体排序只能用窗口状态聚合。这时候你在 438 题里理解的“进出各更新一次”的思路直接就能迁移过去。所以我会说这道题的意义不只是 AC 一个题而是帮你建立一种处理连续数据的直觉能用增量更新解决的问题就不要每次都从头计算。这个直觉比记住那几十行代码值钱得多。我自己的习惯是遇到窗口类题目先画一个很朴素的“进一出再比较”的流程把代码写出来之后再考虑要不要上双指针或者 diff 优化。实际面试里往往把定长滑窗版本讲清楚面试官就已经满意了能主动补充双指针思路属于加分项。最后再提醒一句写完了务必拿重复字符和重叠窗口的用例跑一遍这题的大坑几乎都藏在这两个词里。