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-m1 ... 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 * m log m)O(m)高需排序数据量小仅作思路验证固定窗口 频次数组O(n * 26)O(26)中比较两个长度为 26 的数组大多数常规场景双指针 diff 计数O(n)O(26)低仅维护 count 变量大数据量、需要极致性能表中的时间复杂度一栏我把固定窗口的复杂度写成 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 cbaebabacdp abcm 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.10s的长度为 10 万p的长度为 5000字符集是小写字母。结果大致如下实现方式平均耗时排序比较法超过 60 秒直接放弃固定窗口 频次数组约 45 毫秒双指针 diff 计数约 38 毫秒排序比较法在数据稍微大一点后基本不可用固定窗口和 diff 方法的差距没有想象中大。如果你的代码主要跑在 Python 这种解释型语言里瓶颈往往不在比较而在 Python 循环本身的解释开销。所以选哪种方案更取决于你的代码可读性和维护成本。不过如果你用的是 C 或 Java 这类编译型语言diff 方法的优势会更明显因为数组的逐元素比较可以被编译器优化得很快而 diff 方法能把这个比较从 26 次减少到常数次差距会拉大。7.1 工程代码中的空间优化思路如果你在工程中需要长时间统计字符频次而不是一次性完成任务那么长度为 26 的数组显然是首选。但如果你需要同时维护多个类似窗口可以考虑复用同一个数组通过传入不同的偏移量来区分避免大量内存分配。另一种空间优化思路是不使用数组的完整 26 个位置而是用两个set记录当前窗口中出现的字符种类然后比较这两个set是否相等。不过这个方法只适用于字符种类远小于字符集大小的情况而且要频繁创建set对象性能不一定好。不建议在核心路径上使用。8. 我的实际做题心得与思路总结这道题我前前后后做过不下十遍每次做都有新的体会。最初是为了应付面试刷了几遍模板后来给团队做代码培训时重新推导了 diff 方法的数学逻辑再后来在文本处理的工程项目中把它演化成了处理字符流异位词检测的工具。每一次重新面对它都能从某个细节里得到新的理解。如果要我说这道题最核心的启发那一定是不要急于写代码先把“比较两个字符串是否异位词”这个子问题的最优解法想清楚。很多人卡在这道题上不是不会滑动窗口而是没有意识到“异位词比较”本身就是可以 O(1) 完成的操作。其次我建议你用自己的语言把滑动窗口的模板整理一遍不要直接背别人的代码。逻辑可以是这样初始化窗口左右边界为 0。右边界不断右移把新字符纳入窗口并更新状态。当窗口长度或内容不满足条件时左边界右移缩窄窗口并更新状态。当窗口满足条件时记录答案并继续移动右边界。这个模板可以适配滑动窗口系列的大部分题目。Find All Anagrams in a String 是其中最简单的一类因为窗口长度固定最小覆盖子串则是在这个模板上加入了收缩条件。最后我想强调一个容易被忽略的心态问题写这类题目时不要怕“暴力解法超时”。暴力解法的作用是帮我们验证对题意的理解确认结果的正确性。你完全可以先写出暴力解法再用它作为基准去验证优化版本的输出是否一致。我自己的开发流程里经常会在本地写一个暴力解和一个优化解然后用随机数据对拍确保优化版本没有引入逻辑错误。这个习惯我从刷题一直带到了实际工作中很多重构和性能优化我都用同样的方法验证先保留旧实现作为基准新实现跑同一批数据逐条对比输出。这种做法看着笨但能帮你避免大量“觉得优化对了但实际错了”的尴尬情况。