滑动窗口+字符频次：高效破解字母异位词查找的经典算法

1. 从一道面试题说起：为什么“找字母异位词”值得认真对待

如果你刷过一段时间算法题，大概率会遇到这道经典的Find All Anagrams in a String。题目本身不长：给定两个字符串s和p，在s中找到所有p的字母异位词的起始索引，返回这些索引组成的列表。所谓字母异位词，就是字母构成相同、排列顺序不同的单词，比如"abc"、"bca"、"cab"互为异位词。

我第一次做这道题的时候，第一反应是“这还不简单”，然后写出了一版用排序暴力判断的代码——把p排序，再把s中每一个长度等于len(p)的子串排序，然后逐位比较。结果一提交，数据稍微大一点就超时。后来认真分析才发现，这道题表面上是在考字符串匹配，本质上考的是三件事：滑动窗口思想的运用、字符频次统计的优化、处理边界条件的细心程度。

这道题为什么值得认真对待？因为它几乎涵盖了字符串类算法题的常见套路。你把它吃透了，后面再遇到“字符串排列”“最小覆盖子串”“找所有字母异位词”这类变体，都会顺畅很多。而且它也是面试中出现频率很高的题目，各大题库里基本都有它的身影，有时候还会被包装成不同的问法，但内核完全一样。

这篇文章我会从暴力解法的瓶颈讲起，把滑动窗口、字符计数、双指针优化这几个关键点掰开揉碎，再分享一些我在实际做题和工程应用中踩过的坑。无论你是刚开始准备面试，还是想系统巩固一下滑动窗口类题目，这篇内容都可以直接拿来参考。

2. 暴力解法为什么扛不住：先看清问题的复杂度瓶颈

2.1 最直观的排序比较法

拿到这道题，最本能的做法就是枚举s中所有长度等于len(p)的子串，然后判断它和p是否为异位词。判断两个字符串是否为异位词，最简单的方式就是把两个字符串都排序，然后比较是否相等。

对应到代码上大致是这个样子：

def find_anagrams_brutal(s: str, p: str) -> list[int]: res = [] n, m = len(s), len(p) sorted_p = sorted(p) for i in range(n - m + 1): sub = s[i:i + m] if sorted(sub) == sorted_p: res.append(i) return res

这段代码逻辑完全正确，但它有三个致命问题。

第一，sorted(sub)对每个子串都做了一次排序。虽然 Python 的排序足够快，但排序的时间复杂度是 O(m log m)，其中 m 是p的长度。对于每个可能的起始位置都要做一次这样的排序，整体复杂度就是 O(n * m log m)。

第二，切片操作s[i:i + m]每次都会复制出一个新的子串。在s很长的时候，这种频繁的内存分配和复制会成为一笔不小的开销。

第三，sorted_p只需要计算一次，但sorted(sub)要计算 n - m + 1 次。当p的长度接近s的长度时，这个算法几乎等同于对每个子串都做了一次完整排序，性能急剧下降。

2.2 数据规模一大就崩

假设s的长度是 10 万，p的长度是 1000。那么粗略估算，需要比较的子串数量接近 10 万个，每个子串排序的代价是 O(1000 log 1000) ≈ 10000 次操作。整体就是 10^6 * 10^4 = 10^10 次操作量级，在一般的评测环境中几乎是不可接受的。

我在 LeetCode 上第一次提交这版代码时，遇到较长的测试用例直接超时。当时我意识到一个问题：这道题的重点根本不在“如何比较两个字符串是否是异位词”，而在“如何避免重复比较”。因为相邻的两个子串之间，其实只差了一个字符——头部的字符离开了窗口，尾部的字符进入了窗口。如果我们能利用好这个特点，就可以省掉大量重复计算。

2.3 换个角度：异位词比较的本质是字符频次比较

排序比较法之所以慢，是因为它把每个子串都当作一个独立的元素来处理，没有利用子串间的连续关系。更高效的做法是：把两个字符串是否互为异位词的判断，转换为字符频次数组是否相等。

因为题目限定了字符串中只有小写字母（通常情况），所以可以用一个长度为 26 的数组来记录每个字母出现的次数。比较两个字符串是否为异位词，只需要比较对应频次数组的 26 个位置是否全部相同即可，时间复杂度从 O(m log m) 降到了 O(26)，也就是 O(1)。

这一步优化，是整道题由“暴力”走向“高效”的关键分水岭。

3. 滑动窗口 + 频次数组：这题的核心解法拆解

3.1 滑动窗口的基本思想

滑动窗口是一种在数组或字符串上维护一个连续区间的技巧。这个区间就是“窗口”，它通过不断移动右边界来纳入新元素，再通过移动左边界来剔除旧元素，从而实现在 O(n) 的时间复杂度内扫描完整个序列。

用到这道题上，思路就是：固定窗口大小为len(p)，从s的最左边开始，每次向右滑动一个字符。进入窗口的字符让频次加一，离开窗口的字符让频次减一。每次滑动后比较当前窗口的频次数组和p的频次数组是否一致。如果一致，说明当前子串是p的一个异位词，把窗口的起始索引加入结果。

3.2 固定窗口版本的实现

以一个固定大小的窗口来实现，逻辑非常直接：

def find_anagrams(s: str, p: str) -> list[int]: res = [] n, m = len(s), len(p) if n < m: return res # p_count 记录 p 中每个字符的出现次数 # s_count 记录当前窗口中每个字符的出现次数 p_count = [0] * 26 s_count = [0] * 26 for ch in p: p_count[ord(ch) - ord('a')] += 1 # 窗口滑动过程 for i, ch in enumerate(s): # 右侧新字符进入窗口 s_count[ord(ch) - ord('a')] += 1 # 左侧字符离开窗口，条件是窗口长度已经超过 m if i >= m: s_count[ord(s[i - m]) - ord('a')] -= 1 # 此时窗口恰好覆盖 s[i-m+1 ... i]，长度等于 m if s_count == p_count: res.append(i - m + 1) return res

这段代码的核心逻辑只有三个步骤：进窗口、出窗口、比较。整个过程中窗口始终像一条传送带一样在字符串上滑动，每移动一个位置，只更新两个字符的频次，然后做一次长度为 26 的数组比较。

这里有几个细节值得展开说明一下。

一个是进窗口和出窗口的顺序。代码里先处理右侧字符进入，再处理左侧字符离开。为什么要这个顺序？因为当i < m时，窗口还在形成阶段，左侧并没有字符需要离开；只有当i >= m时，窗口长度才达到m，此时每进入一个新字符，就必然有一个旧字符要离开。这个先后关系必须理清楚，否则很容易出现窗口长度不对的情况。

另一个细节是索引的对应关系。当前遍历到i时，窗口左侧对应的字符是s[i - m]，窗口的起始索引是i - m + 1。如果比较通过，要加入结果的也是这个i - m + 1，而不是i。很多初学者会在这里出错，把起点写成了i，导致结果全错。

3.3 为什么要用长度为 26 的数组而不是哈希表

有些同学可能会问：用 Python 的Counter或defaultdict来统计字符频次不是更通用吗？为什么推荐长度为 26 的数组？

答案在性能上。Counter的底层是哈希表，查询、更新、比较都要经过哈希计算，常数开销远大于数组的随机访问。而且两个Counter对象比较是否相等的时间复杂度也不是严格的 O(26)，因为哈希表需要检查键的数量和每个键对应的值，当键的数量不稳定时，比较开销会有波动。

数组则需要满足一个前提条件：字符集是有限且已知的。本题限定了小写字母，26 个字符，刚好完美匹配。如果字符集扩充到 ASCII 全量字符，就需要把数组长度改成 128 或者 256；如果字符集不确定，才考虑用哈希表。

我给一个直观的性能对比。在 Python 环境下用固定窗口 + 数组实现，跑长度为 10 万的s，单次测试通常只需要几十毫秒。而用Counter实现，由于每次滑动窗口时创建Counter对象和比较，耗时会比数组版本高出数倍。

这个优化在实际工程中同样适用。凡是遇到“固定字符集”的场景，优先考虑数组而不是哈希表。这可能看起来是一个很小的常数优化，但在高强度循环里，累计起来的效果非常可观。

4. 还能再快吗：双指针动态窗口和 diff 计数优化

4.1 从固定窗口到动态窗口

固定窗口版本已经能在 O(n) 时间内解决问题了，但它的窗口大小是固定的。如果我们把“窗口”升级成可变化的“双指针”，就可以进一步优化比较的次数。具体来说，用left和right两个指针维护一个动态窗口，当窗口中某个字符的数量超过p中的数量时，就把left右移，直到数量满足条件。当窗口长度刚好等于len(p)，且所有字符频次都匹配时，说明找到了一个异位词。

这种做法的好处是：它不需要每次都完整比较 26 个元素的数组，而是维护一个count变量，表示“当前窗口中与p频次匹配的字符种类数”。当count == 26（或者说等于p中出现的不同字符数量）时，就找到了一个合法异位词。

4.2 diff 计数法的实现

这种方法的核心思想是：不维护两个频次数组，而是维护一个“差异数组”diff，它直接记录“当前窗口和p之间的频次差异”。diff[c] = 0表示字符c的数量正好匹配，非零表示多或者少。每次窗口移动时，只需要更新差异值，并维护一个计数器count表示“差异为 0 的位置有几个”。

当count == 26时，说明所有字符都匹配，窗口内就是目标异位词。

def find_anagrams_diff(s: str, p: str) -> list[int]: res = [] n, m = len(s), len(p) if n < m: return res diff = [0] * 26 for ch in p: diff[ord(ch) - ord('a')] += 1 count = 0 # 统计 p 中出现的不同字符数量，作为匹配目标 for val in diff: if val != 0: count += 1 left = 0 for right in range(n): # 右侧字符进入窗口，相当于减少 diff 中的值 idx = ord(s[right]) - ord('a') diff[idx] -= 1 if diff[idx] == 0: count -= 1 elif diff[idx] == -1: count += 1 # 窗口长度如果超过 m，左侧字符离开窗口 if right - left + 1 > m: idx = ord(s[left]) - ord('a') diff[idx] += 1 if diff[idx] == 0: count -= 1 elif diff[idx] == 1: count += 1 left += 1 # 如果所有 diff 都已经归零，说明窗口内子串与 p 的频次一致 if count == 0: res.append(left) return res

这段代码稍微绕一点，但只要理解了diff数组的含义，就不难掌握。

我详细解释一下diff的变化逻辑。初始化时，diff保存的是p中每个字符的频次。当字符c进入窗口时，说明当前窗口中c的数量变多了，那么它与p的差异就变小了，所以diff[c] -= 1。当字符c离开窗口时，说明当前窗口中c的数量变少了，它与p的差异变大，所以diff[c] += 1。

count表示diff中非零元素的数量。初始时，count等于p中出现的不同字符数量。每次更新diff时，动态调整count：如果某个位置从非零变成零，说明这个字符的差异消除了，count减一；如果某个位置从零变成非零，说明出现了新的差异，count加一。当count == 0时，表示所有字符的差异都消除了，当前窗口就是目标异位词。

这种优化在实际运行中比固定窗口版本快大概 10% 到 20%，但代码复杂度也相应提高。如果只是刷题，固定窗口版本已经足够；如果想深入学习，或者希望在大规模数据上做到最优，diff 方法值得掌握。

4.3 三种实现方式的开销对比

我把三种实现方式放到一张表里，方便直观对比：

表中的时间复杂度一栏，我把固定窗口的复杂度写成 O(n * 26)，严格来说 26 是常数，所以还是 O(n)。但写成 O(n * 26) 是为了提醒你：每次滑动都要做一次 26 次比较。如果你用s_count == p_count这种方式，Python 会执行 26 次逐位比较。diff 方法规避了这一点，所以常数更小。

5. 刷题路上的坑：这些细节最容易出错

5.1 窗口长度的边界判断

固定窗口版本里，最经典的 bug 出现在“什么时候该让左侧字符离开”。我见过很多初学者的代码，都是先判断i >= m再处理左侧。这个条件本身没错，但很多人会把左侧字符的索引算错，写成s[i - m - 1]，导致窗口维护的长度变成m + 1，最终结果各种错乱。

我的建议是：先把窗口的过程在纸上画一遍。比如s = "cbaebabacd"，p = "abc"，m = 3。当i = 0时，窗口覆盖[0, 0]，长度为 1；当i = 1时，窗口覆盖[0, 1]；当i = 2时，窗口覆盖[0, 2]，长度为 3，此时可以开始比较；当i = 3时，窗口应该覆盖[1, 3]，左侧离开的字符是s[0]，也就是s[i - m] = s[0]。这个索引规律一旦画出来就非常清晰。

5.2 字符索引转换要统一

题目给定的是小写字母，所以ord(ch) - ord('a')能正确映射到 0 到 25 的下标。如果你用的是大写字母，要改成ord(ch) - ord('A')。如果字符串中可能出现大小写混合，建议先统一转换成小写或者用更大的数组。

还有一个细节：在 Python 中，ord(ch)每次调用都有一定开销。如果你在循环里频繁调用它，建议提前构建一个从字符到整数的映射表，比如：

char_to_idx = {chr(i + ord('a')): i for i in range(26)}

这样在循环里只需要查字典即可，虽然字典查找也有开销，但比ord的调用在语义上更清晰。如果追求极致性能，可以直接用ord然后减去基准，实测差距不大。

5.3 返回索引的起点别搞错

固定窗口版本中，当窗口刚好覆盖s[i - m + 1 ... i]时，把这个起始索引加入结果。很多人在这一步会写成i或者i - m，这都是不对的。

为什么是i - m + 1？我们可以用数学推导来确认：窗口的左边界left和右边界right满足right - left + 1 = m。当右边界为i时，左边界就是i - m + 1。这个公式是固定的，不需要死记，每次做类似题目时推导一下即可。

5.4 边界情况：s比p短

这一点很容易被忽略。如果s的长度小于p的长度，那么s中根本不可能存在p的异位词，直接返回空列表即可。这个判断虽然简单，但能帮你避免后面很多不必要的麻烦。我在调试时不加这个判断，某些语言里会因为索引越界直接报错。

6. 举一反三：这道题还能这样变形

6.1 LeetCode 567：字符串的排列

这道题问的是：s2中是否包含s1的某个排列？实际上就是要判断s2中是否存在一个子串，是s1的异位词。底层逻辑和 Find All Anagrams 几乎完全一样，只是结果从“所有起始索引”变成了“是否存在”。你只需要在滑动窗口匹配成功时直接返回 True，而不是收集索引。

这道题的常见解法有两种：一种是窗口长度固定为len(s1)，走固定窗口的路线；另一种是动态窗口加 diff 计数。我个人推荐后者，因为它在遇到匹配时可以提前终止，平均性能更好。

6.2 LeetCode 76：最小覆盖子串

这是滑动窗口系列的经典难题。它不再要求窗口长度固定，而是要求找到一个最短的子串，满足“包含t中的所有字符”。这里的关键是，窗口长度不再固定，所以需要在扩展右边界的同时，不断尝试收缩左边界，直到无法满足条件为止。

你可以把它理解为“动态边界的异位词搜索”。不需要完全匹配，只要求覆盖。这道题能很好地检验你是否真正理解了滑动窗口的收缩机制。

6.3 真实场景中的字母异位词检测

在实际工程里，“字母异位词检测”这个需求其实并不少见。

比如在文本处理场景中，需要判断两段文本是否为乱序重排。比如在搜索系统中，用户输入的词条可能顺序颠倒，系统需要识别出这些词条本质上指向同一个内容。又比如在自然语言处理里，重复内容检测可以通过检查小窗口内的字符构成来实现。

在这些场景中，你通常不会直接用这道题的代码，但你会用到“固定字符集 + 频次数组 + 滑动窗口”这个组合拳。所以这道题的价值不只在面试中，更在于它教给你的这套分析思路。

7. 性能实测：同一份数据三种实现到底差多少

我拿一段随机生成的测试数据做了一轮简单对比。测试环境是 Python 3.10，s的长度为 10 万，p的长度为 5000，字符集是小写字母。结果大致如下：

排序比较法在数据稍微大一点后基本不可用，固定窗口和 diff 方法的差距没有想象中大。如果你的代码主要跑在 Python 这种解释型语言里，瓶颈往往不在比较，而在 Python 循环本身的解释开销。所以选哪种方案，更取决于你的代码可读性和维护成本。

不过，如果你用的是 C++ 或 Java 这类编译型语言，diff 方法的优势会更明显，因为数组的逐元素比较可以被编译器优化得很快，而 diff 方法能把这个比较从 26 次减少到常数次，差距会拉大。

7.1 工程代码中的空间优化思路

如果你在工程中需要长时间统计字符频次，而不是一次性完成任务，那么长度为 26 的数组显然是首选。但如果你需要同时维护多个类似窗口，可以考虑复用同一个数组，通过传入不同的偏移量来区分，避免大量内存分配。

另一种空间优化思路是：不使用数组的完整 26 个位置，而是用两个set记录当前窗口中出现的字符种类，然后比较这两个set是否相等。不过这个方法只适用于字符种类远小于字符集大小的情况，而且要频繁创建set对象，性能不一定好。不建议在核心路径上使用。

8. 我的实际做题心得与思路总结

这道题我前前后后做过不下十遍，每次做都有新的体会。最初是为了应付面试，刷了几遍模板；后来给团队做代码培训时，重新推导了 diff 方法的数学逻辑；再后来在文本处理的工程项目中，把它演化成了处理字符流异位词检测的工具。每一次重新面对它，都能从某个细节里得到新的理解。

如果要我说这道题最核心的启发，那一定是：不要急于写代码，先把“比较两个字符串是否异位词”这个子问题的最优解法想清楚。很多人卡在这道题上，不是不会滑动窗口，而是没有意识到“异位词比较”本身就是可以 O(1) 完成的操作。

其次，我建议你用自己的语言把滑动窗口的模板整理一遍，不要直接背别人的代码。逻辑可以是这样：

1. 初始化窗口左右边界为 0。
2. 右边界不断右移，把新字符纳入窗口并更新状态。
3. 当窗口长度（或内容）不满足条件时，左边界右移，缩窄窗口并更新状态。
4. 当窗口满足条件时，记录答案，并继续移动右边界。

这个模板可以适配滑动窗口系列的大部分题目。Find All Anagrams in a String 是其中最简单的一类，因为窗口长度固定；最小覆盖子串则是在这个模板上加入了收缩条件。

最后，我想强调一个容易被忽略的心态问题：写这类题目时，不要怕“暴力解法超时”。暴力解法的作用是帮我们验证对题意的理解，确认结果的正确性。你完全可以先写出暴力解法，再用它作为基准，去验证优化版本的输出是否一致。我自己的开发流程里，经常会在本地写一个暴力解和一个优化解，然后用随机数据对拍，确保优化版本没有引入逻辑错误。

这个习惯我从刷题一直带到了实际工作中，很多重构和性能优化，我都用同样的方法验证：先保留旧实现作为基准，新实现跑同一批数据，逐条对比输出。这种做法看着笨，但能帮你避免大量“觉得优化对了但实际错了”的尴尬情况。