企业官网建设流程全解析

力扣438题，找到字符串中所有字母异位词，是我刷力扣热题100时反复回头看了三遍的一道题。原因很简单：第一遍我用排序暴力解，提交直接超时；第二遍我学会了滑动窗口，总算AC了；但直到第三遍我看到别人用diff计数把判断开销压到O(1)时，才意识到这道题能在"已经会滑动窗口"的人群里继续筛人。如果你也在用Python刷题，这篇笔记会包含我从超时到AC的全过程，以及代码层面容易踩的几个坑。

1. 为什么一道中等题值得我单独写笔记

1.1 题目描述与数据范围拆解

题目本身很简洁：给定两个字符串s和p，找到s中所有p的字母异位词的子串，返回这些子串的起始索引。字母异位词指字母相同但排列不同的字符串。

两个示例很典型：

• s = "cbaebabacd", p = "abc"时，输出[0, 6]。s[0:3]是"cba"，s[6:9]是"bac"，都是"abc"的重新排列。
• s = "abab", p = "ab"时，输出[0, 1, 2]。三个连续窗口"ab"、"ba"、"ab"都满足条件。

数据范围是容易被忽略的重点：s和p的长度都在1到310^4之间，字符串只包含小写字母。310^4这个量级意味着O(n^2)级别的代码大概率过不了，而涉及字符串切片排序的写法在极端情况下会非常慢。只包含小写字母这一点也很重要，它决定了我们可以用长度为26的数组来计数，而不是必须依赖哈希表。

1.2 面试官为什么偏爱这道题

我在准备面试的过程中明显感觉到，438这道题在算法题单里出现频率相当高。核心原因是它把几个基础考点巧妙地组合在了一起：哈希计数、双指针、字符串子串处理。它不像动态规划那样需要比较巧妙的推导，更多是在考察基本功是不是扎实。

而且这道题有天然的复杂度层次。新手会用暴力排序，有一定经验的会用Counter维护窗口，真正理解滑动窗口状态的人能写出diff优化版本。同一个题能看出候选人处在哪个阶段，这是面试官最看重的区分度。再加上它和力扣567（字符串的排列）、力扣76（最小覆盖子串）都有直接关联，把438吃透了等于同时给那两个题打了底子。

2. 破题关键：异位词比较的是频次，不是顺序

2.1 先写一版必然超时的暴力解法

我第一次提交的代码长这样：

class Solution: def findAnagrams(self, s: str, p: str) -> List[int]: n, m = len(s), len(p) sorted_p = sorted(p) res = [] for i in range(n - m + 1): if sorted(s[i:i+m]) == sorted_p: res.append(i) return res

逻辑完全正确，样例也能过，但提交后立刻超时。原因在于复杂度：枚举所有起点需要O(n)，每个起点要做一次切片和排序，排序是O(m log m)，整体就是O(n * m log m)。当n和m都接近3*10^4时，这个量级根本跑不动。

这个暴力版本也有它的价值。它让我意识到一件事：判断两个字符串是否互为字母异位词，本质上是比较它们的字符频次是否完全一致，而不是比较顺序。排序只是实现"频次一致"的一种笨办法，真正的解法应该直接统计数量。

2.2 滑动窗口为什么能省掉重复计算

如果不用滑动窗口，只把排序换成Counter，每个起点都重新统计窗口内字符，复杂度是O(n*m)，依然不够好。滑动窗口的核心洞察在于：相邻两个窗口的差异极小。

窗口s[i:i+m]和窗口s[i+1:i+1+m]之间，只发生了两件事：s[i]离开了窗口，s[i+m]进入了窗口。中间的m-2个字符根本没有变化。既然大部分字符没动，那它们的计数也完全不需要重新计算。我们只需要在原有计数基础上，给离开的字符减一，给进入的字符加一，就能得到新窗口的频次状态。

这一步优化让单次窗口移动的成本从O(m)降到了O(1)，整体复杂度变成O(n)。这也是滑动窗口类题目最核心的思想：状态是增量更新的，而不是每次从零构建。

2.3 两种计数结构的选择

窗口内频次用什么存，在Python里主要有两个选择。

一是collections.Counter。它本质是字典的子类，直接支持Counter之间的比较，代码写起来非常清爽。缺点是每次比较两个Counter要遍历所有key，不过因为字符集只有26个，实际开销可控。

二是长度为26的数组。用小写字母的ASCII码做索引，s_count[i]表示字符chr(i+97)在窗口中出现的次数。数组的更新和访问都是O(1)，配合diff变量可以让"窗口是否满足条件"的判断也变成O(1)。

具体场景下我的选择标准是：日常刷题用Counter版本，因为可读性好；如果数据量再大一个量级，或者面试官追问"能不能再快一点"，就切到数组diff版本。

3. 两种Python解法的完整实现与逐行拆解

3.1 Counter版本：最符合直觉的写法

from collections import Counter class Solution: def findAnagrams(self, s: str, p: str) -> List[int]: n, m = len(s), len(p) if n < m: return [] need = Counter(p) cur = Counter() ans = [] left = 0 for right in range(n): cur[s[right]] += 1 if right - left + 1 > m: left_char = s[left] if cur[left_char] == 1: del cur[left_char] else: cur[left_char] -= 1 left += 1 if cur == need: ans.append(left) return ans

这段代码是标准的定长滑动窗口框架。left和right分别指向当前窗口的左右边界，窗口内的字符就是s[left:right+1]。每轮循环先加入右边的字符，然后检查窗口长度是否超过了m，如果超过就把左边的字符移出去，最后比较cur和need。

这里有一个细节必须注意：当某个字符的计数减到0时，一定要用del把这个key从Counter里删掉。我见过不少人在这一步翻车——Counter里留着{'a': 0}这样的键值对，虽然人为看觉得没问题，但Python在比较两个Counter时是逐key比较的，多出来一个值为0的key会导致比较结果不相等。这个坑在后面专门讲。

3.2 数组diff版本：让判断成本降到O(1)

class Solution: def findAnagrams(self, s: str, p: str) -> List[int]: n, m = len(s), len(p) if n < m: return [] p_count = [0] * 26 s_count = [0] * 26 for ch in p: p_count[ord(ch) - ord('a')] += 1 diff = 0 for i in range(26): if p_count[i] != 0: diff += 1 ans = [] left = 0 for right in range(n): idx = ord(s[right]) - ord('a') if s_count[idx] == p_count[idx]: diff += 1 s_count[idx] += 1 if s_count[idx] == p_count[idx]: diff -= 1 if right - left + 1 > m: idx = ord(s[left]) - ord('a') if s_count[idx] == p_count[idx]: diff += 1 s_count[idx] -= 1 if s_count[idx] == p_count[idx]: diff -= 1 left += 1 if diff == 0: ans.append(left) return ans

diff这个变量是整个优化的灵魂。它的含义是：当前窗口中，字符频次与p不一致的字符种类数。当diff等于0时，说明窗口内所有字符的频次都跟p完全一致，这个窗口就是p的一个字母异位词。

diff初始值不是0，而是p中不同字符的种类数。因为初始窗口是空的，所有字符计数都是0，而p中出现的那些字符目标计数大于0，所以它们都是不一致的。比如p是"aab"，p_count里a为2，b为1，初始diff就是2。

3.3 为什么diff的更新顺序不能乱

diff版本里每一处的顺序都经过精心设计。以右端加入字符为例：

1. 先判断加入前的状态。如果s_count[idx]等于p_count[idx]，说明这个字符当前是一致的。现在要给它加一，加完之后必然不一致，所以diff先加一。
2. 执行真正的计数更新s_count[idx] += 1。
3. 再判断加入后的状态。如果更新后的s_count[idx]等于p_count[idx]，说明这个字符从不一致回到了不一致？不对，是从原来的状态变成了新的不一致，所以diff减一。

这两次判断合起来的逻辑是：只有在字符的一致性状态发生翻转时，才改变diff。如果加入前不一致、加入后也不一致，diff是不动的。这种写法比"每次都重新统计diff"高效得多，但也容易写错。我自己写过一版把判断和更新顺序搞反的代码，结果后半段的答案全部错位。建议拿到这段代码后手动跑一个简单例子，比如s="abab",p="ab"，跟着right从0走到3，把每个diff值写下来，很快就能理解。

左端移除字符的逻辑完全对称。这里就不重复解释了，但是要注意一下left的移动时机：先更新计数，再left += 1，因为left指向的是即将被移出窗口的字符。

4. 边界条件与真实踩坑记录

4.1 s比p短，直接返回空列表

这是我第一次提交时忽略的条件。s_len < p_len时，s里根本不存在长度等于p的子串，无论如何都找不到异位词。如果不加这个判断，后面的循环里会出现负数索引或者窗口长度始终小于m的情况，结果虽然不报错但答案肯定是错的。

在Counter版本中这个问题表现为：left和right的窗口始终撑不满，cur永远不会等于need，最终返回空列表。看上去碰巧对了，但一旦后面加了diff优化，初始diff是根据p计算的，窗口长度不够时diff可能不为0，也可能出现难以预料的比较结果。所以无论写哪个版本，先把长度判断写上是好习惯。

4.2 窗口索引差一个1的惨案

定长窗口最容易错的地方是left的收缩条件。错误的写法是把if right - left + 1 > m写成if right - left + 1 >= m，或者把left_char取成s[left]还是s[right - m]搞混。

这两种写法都会让窗口的长度差1。假设p的长度是3，正确窗口长度应该始终是3，但错误代码可能让窗口变成2或4。窗口太大时会多算字符，窗口太小时又会漏掉字符。有一个很实用的自查技巧：在循环里加两行临时打印，输出每次循环结束后的窗口子串和left、right值，跑一遍小样例，立刻能看出来窗口是否符合预期。

4.3 Counter的del陷阱：计数归零后key还在

这个问题我印象太深了。Counter版本中，如果left_char的计数减到0，但没有del，而是留着cur[left_char] = 0，那么比较cur == need时就会出问题。比如need是Counter({'a': 1, 'b': 1})，cur里如果多了个'c': 0，两个Counter就不相等，明明窗口内容是对的却匹配不上。

处理方式有两种：

• 每次减到0就del当前key；
• 或者比较时用if cur == need，但确保cur里永远不出现值为0的key。

我建议坚持用第一种方式，把它变成肌肉记忆。因为LeetCode的环境里同一段代码会被大量测试用例反复调用，只要有一个用例触发这个情况就会失败，而这种失败特别难排查。

4.4 重复字符多的场景：为什么"abab"能返回三个答案

有读者可能会疑惑，s="abab", p="ab"时，索引0的"ab"、索引1的"ba"、索引2的"ab"都算异位词，这要求滑动窗口在移动时不会因为字符重复而漏判。

实际上重复字符并不影响算法正确性。关键是我们在每个right位置结束后都检查一次当前窗口，而窗口长度始终保持在2。right=1时窗口是"ab"，right=2时窗口是"ba"，right=3时窗口是"ab"。三个窗口各自独立判断，互不影响。diff版本里，重复字符会导致s_count某个位置大于p_count，这时diff会正确变成非零值，不会误判。

5. 从438到567和76：滑动窗口的通用模板

5.1 定长窗口的通用写法

438题让我提炼出了一个定长窗口的通用模板：

left = 0 for right in range(n): 更新窗口状态(加入s[right]) if right - left + 1 > k: # k是固定窗口长度 更新窗口状态(移除s[left]) left += 1 if 当前窗口满足条件: 记录答案

这个模板的适用范围很广。凡是题目里出现"连续子串""固定长度子数组"这类字眼，都可以先套这个框架再针对条件做修改。438题的条件是"频次相等"，567题的条件也是"频次相等"，只是返回变成布尔值。

力扣567题"字符串的排列"判断的是s2中是否存在s1的任意一种排列。把438的返回值从列表改成True/False就是567的解法。我建议做438时顺手把567也写一遍，两道题连在一起刷记忆非常牢固。

5.2 可变窗口：76题的变形思路

力扣76题"最小覆盖子串"是另一个方向的变体。它不要求窗口长度固定，而是要求窗口能覆盖t中的所有字符，然后找最短的窗口。这个题就不能用定长模板了，因为窗口长度是动态变化的。

但解决思路仍然和438一脉相承：用计数结构维护窗口状态，用某个变量记录"是否有资格收缩窗口"。76题里通常会统计一个"还需要多少种字符才能覆盖"，当这个值为0时尝试收缩左边界，寻找更短的有效窗口。如果你把438的diff概念理解了，76题需要的那个"缺失字符种类数"就不会觉得陌生。它本质上也是diff，只是把更新逻辑从定长移到变长。

5.3 我自己的刷题体会

根据我个人的经验，438这道题值得用三个晚上分三次刷。第一次用Counter版本跑通，第二次照着diff版本自己默写，第三次尝试不看代码把两种解法都写出来并解释给虚拟听众。这个流程走完，滑动窗口的定长场景基本就过关了。

再补充一个实用技巧：在力扣的Python环境里，提交代码时不用显式导入List这类类型，但在本地调试时要记得from typing import List。另外ord(ch) - ord('a')是数组版本的惯用索引方式，不要试图用ord(ch) - 97来省那一点时间，可读性下降完全不值得。

最后说点题外话。我见过不少人刷题时只看题解然后背代码，遇到438这种题背一遍Counter版本就过了。但如果你把diff版本也吃透，以后再遇到"窗口状态需要O(1)判断"的变体，会明显比只背一种写法的人从容得多。算法题刷得多了会发现，真正拉开差距的不是你会不会背模板，而是你理解不理解模板里那个变量为什么需要存在。438就是帮你建立这种理解的好题目。