找到字符串中所有字母异位词

这道题真正在问什么

给字符串 s 和 p，找出 s 中所有「p 的字母异位词」子串的起始下标。异位词指字母种类和各自的个数都完全相同、只是排列顺序不同，比如 "cba" 是 "abc" 的异位词。题目里藏着一个决定解法形态的事实：异位词的长度必然等于 p 的长度——这直接把问题变成「检查 s 中每个长度为 len(p) 的窗口」。比如 s = "cbaebabacd"、p = "abc"，答案是 [0, 6]。

为什么想到定长滑动窗口

暴力做法是对每个起点截出长 k = len(p) 的子串，排序后和排序过的 p 比对，每个起点花 O(k log k)，整体 O(n · k log k)，重复劳动很多。

关键观察是：判断异位词根本不需要顺序信息，只需要「每个字母出现几次」这份统计；而相邻两个窗口只差两个字符——左端少一个、右端多一个，其余 k - 1 个字符原封不动。既然统计量只有两处变化，就没理由每次推倒重算，把计数表增量地改两格就够了。这正是定长滑动窗口的用武之地。

窗口计数怎么维护，何时判定命中

先统计 p 的字符计数 need，再统计 s 前 k 个字符组成的初始窗口计数 win，两表相等则下标 0 记入答案。之后窗口每右移一格：新进的字符 s[r] 计数加一，移出的字符 s[r - k] 计数减一（减到 0 就把该键删掉，保证两张表能直接判等），然后比较 win 与 need，相等就把起点 r - k + 1 记入答案。

全程保持的不变量是：win 永远精确等于当前窗口内各字符的出现次数。因此「win == need」当且仅当窗口是 p 的异位词，判定既不漏也不多。

为什么必须比次数而不是只比种类

p 里的字母可能重复，比如 p = "aab"：窗口 "abb" 字母种类和 p 一样是 {a, b}，但个数对不上，不是异位词。只用集合判断会放过这类假货，必须逐字母比较出现次数。

另一个方向的错误是让窗口变长变短——本题窗口大小恒等于 k，一旦写成「凑齐了就收缩」的变长窗口套路反而复杂化。定长窗口和变长窗口（如 LeetCode 76 最小覆盖子串）是滑动窗口的两个分支，本题因为「异位词长度确定」落在定长这一支，代码也因此更简单：右端每进一个，左端必出一个。

复杂度怎么算，边界在哪里

时间 O(n)：窗口右端把 s 扫一遍，每步做两次计数增减加一次计数比较；字母表固定 26 个小写字母，比较是 O(26) 的常数操作。空间 O(1)：两张计数表至多各存 26 个键，不随 n 增长。

最先要防的边界是 len(s) < len(p)：窗口根本摆不下，直接返回空数组，否则初始窗口的截取就会出错。另外结果记录的是起点 r - k + 1 而不是右端 r，下标换算写错一格，答案会整体偏移。