如果你在 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 开始到 start+m-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 = "cbaebabacd"，p = "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 = "abab"，p = "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 = "abbbac"，p = "abc"，某个瞬间窗口可能是 "abbba"，里面 a、b 都有，c 也出现过，可窗口长度远大于 3，显然不是异位词。

所以 while 循环里要先检查窗口长度是否等于 np，是就记录，不是就继续收缩，直到 matched 不再等于 np 为止。这里有个小细节：收缩过程中，如果左指针离开的字符并不是 p 需要的字符，比如某个字母完全不在 p 里，对应预算加 1 后可能从负数变 0，matched 不会变，循环会继续收缩。这个行为是故意的，目的是把混进来的无关字符全部排出窗口。

我在第一次写双指针版本时，就是漏了“收缩时 matched 不一定立刻下降”这一点，导致把一些长度不符的窗口也记录进去了。后来我意识到，matched == np只是候选条件，长度相等才是最终条件。

4. 多种实现方案的复杂度对比与选型建议

4.1 四类方案的比较表

把几种思路摆在一起看，差异就很明显了：

严格来说，定长滑窗每次比较两个长度为 26 的数组是 O(26)，所以总复杂度写作 O(26N) 更严谨。但因为 26 是常数，且列表比较在 Python 内部是 C 层完成，实际运行非常快，所以通常直接说是 O(N)。

4.2 实测印象：list 比较 vs Python 循环

我在本地跑过几组测试，s 长度十万级、p 长度几千，定长滑窗数组版大概几十毫秒完成。如果换成 Counter 版本，时间会上升到一两百毫秒，但依然能过。真正慢的是每次都用sorted(s[i:i+m])的版本，十万级输入基本要跑好几秒，完全不是一个量级。

这里有个非常反直觉的结论：定长滑窗的数组版，就算每次移动都比较 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 的长度是 3，p 的长度是 5，s 里根本不可能存在长度为 5 的子串。

第二种：s 和 p 长度相等。此时只需要检查 s 整体是不是 p 的异位词，是就返回[0]，不是就返回[]。定长窗口代码天然能处理这种情况，但双指针版本要注意 left 的移动不能越界。

第三种：p 为空字符串。LeetCode 原题一般保证非空，但在工程思考时还是要问一句。如果按“空串是任何字符串的异位词”来理解，答案可能是所有位置；如果按业务逻辑直接返回空，也合理。面试时把这个歧义主动抛出来，反而显得你考虑周全。

5.2 重复字符与重叠窗口怎么测

字母异位词题目里，p 很可能有重复字符，比如 p = "abab"。这种情况下，计数数组里 a 和 b 都是 2，滑动窗口比较的是“整体频次”，依然能正确处理。但有个容易踩的坑是：看到窗口里有 a 和 b 就觉得满足，忘了数量要对上。

重叠窗口也要重点测。例如 s = "aaaaaa"，p = "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 优化。实际面试里，往往把定长滑窗版本讲清楚，面试官就已经满意了；能主动补充双指针思路，属于加分项。最后再提醒一句：写完了务必拿重复字符和重叠窗口的用例跑一遍，这题的大坑，几乎都藏在这两个词里。