如何找到字符串中所有字母异位词的起始位置？（LeetCode 438）

简化版

给字符串 s 和 p，找出 s 中所有「是 p 的字母异位词」的子串的起始下标。因为异位词长度固定（= p 的长度），用固定大小的滑动窗口：窗口宽度等于 p.length()，在 s 上滑动，维护窗口内每个字母的计数；每滑一格，判断窗口内的字母频次是否和 p 的一致，一致就记录起点。用计数数组 + 一个「匹配的字母种类数」变量可做到 O(n)。

详细版

List<Integer> findAnagrams(String s, String p) {
    List<Integer> res = new ArrayList<>();
    if (s.length() < p.length()) return res;
    int[] need = new int[26], window = new int[26];
    for (char c : p.toCharArray()) need[c - 'a']++;   // p 的字母频次
    int n = p.length();
    for (int i = 0; i < s.length(); i++) {
        window[s.charAt(i) - 'a']++;                  // 右端进入窗口
        if (i >= n) {                                 // 窗口超宽，左端移出
            window[s.charAt(i - n) - 'a']--;
        }
        if (i >= n - 1 && Arrays.equals(window, need)) {
            res.add(i - n + 1);                       // 窗口频次 == p，记录起点
        }
    }
    return res;
}

固定窗口：宽度恒为 p.length()，右端进一个、左端出一个，保持宽度。
判断异位词：窗口内 26 字母计数和 p 的计数数组相等即是异位词。
优化：用「匹配字母种类计数」代替每次 Arrays.equals，可从 O(26n) 降到 O(n)。
复杂度：O(n)（Arrays.equals 版是 O(26n)，常数小）。

完整版教学

一、为什么用「固定大小」滑动窗口

异位词要求字母和数量都和 p 相同，那么长度必然等于 p 的长度。所以我们要找的是 s 中所有「长度 = p.length()、且字母频次 = p」的子串。既然长度固定，就用一个宽度恒定的窗口在 s 上从左滑到右，逐个检查每个位置的窗口是否满足条件——不需要变长窗口。

二、窗口的维护：进一个、出一个

窗口宽度设为 n = p.length()。遍历 s，指针 i 是窗口右端：

右端进入：window[s[i]]++，新字符加入窗口计数。
左端移出：当窗口宽度超过 n（即 i >= n），把最左边的字符 s[i-n] 移出：window[s[i-n]]--。这样窗口始终保持宽度 n。
检查：当 i >= n-1（窗口已满 n 个字符），比较 window 和 need（p 的计数）是否相等，相等则当前窗口起点 i-n+1 是一个答案。

三、判断「频次相等」的两种写法

写法一：Arrays.equals(window, need)。每次比较两个 26 长度数组，O(26)。整体 O(26n)——因为 26 是常数，实践中够快，代码清晰，面试推荐。

写法二：维护「匹配的字母种类数」matched（真正的 O(n)）。用一个变量记录「当前有多少种字母的窗口计数恰好等于 p 的计数」。每次某字母计数变化时，看它是否让 matched 增减，当 matched == 26（或 == p 中不同字母数）时说明完全匹配。省去每次全数组比较。写法二快但易错，面试可先给写法一、提一句可优化。

四、和「最小覆盖子串 / 无重复最长子串」的区别

本题（438）是固定长度窗口——因为异位词长度确定，窗口不伸缩。
最小覆盖子串（76）、无重复字符最长子串（3）是可变长度窗口——右端扩张、左端按条件收缩，找最优长度。

区分标准：「长度已知/固定」用定长窗口，「长度要求最优」用变长窗口。都是滑动窗口家族，但控制方式不同。本题定长最简单。

五、易错点

窗口移出时机：i >= n 才移出左端（前 n-1 步只进不出，把窗口填满）。写成 i >= n-1 会提前移出、窗口不足宽。
记录起点的下标：起点是 i - n + 1（i 是右端，窗口宽 n）。别写成 i - n。
s.length() < p.length()：直接返回空，否则窗口逻辑越界。
字符集：本题只含小写字母，用 int[26]。其他字符集需扩大或用哈希表。

六、固定窗口为何不会漏解

异位词与模式串 p 的长度必然相同，所以窗口长度不是优化选择，而是题意约束。右指针每加入一个字符，当窗口超过 p.length() 就移出最左字符；检查时窗口始终覆盖每个可能的长度 m 子串且只检查一次。

s="cbaebabacd", p="abc", m=3
[0,2] "cba" 频次相同 -> 记录 0
[1,3] "bae" 不同
[2,4] "aeb" 不同
...
[6,8] "bac" 频次相同 -> 记录 6
结果 [0,6]

校验维度	本题必须保持的结论
循环/递推不变量	检查答案时窗口长度恒为 m，窗口计数恰好等于 `s[left..right]` 的字符频次。
边界条件	`p.length()>s.length()` 时没有窗口；若字符集不限小写字母，应换 Map 或扩大计数结构。
复杂度与代价	数组整体比较写法是 O(Σn)，小写字母 Σ=26 可视为 O(n)；差异计数可严格常数判断。
自检方式	用最小输入、典型输入和触及边界的输入分别手推，结果应与定义一致。

这组推演的作用不是替代证明，而是把抽象规则落到每一步状态变化上。面试写完代码后，应主动指出不变量如何保证不漏解，以及边界为何不会越界或死循环。若手推结果与定义不一致，应先修正状态语义，而不是继续给代码打补丁。

七、面试现场如何验证这道题

字符串题首先要固定“处理的是字符、UTF-16 代码单元还是 Unicode 码点”，再讨论下标与窗口。本题应先复述这条不变量：检查答案时窗口长度恒为 m，窗口计数恰好等于 s[left..right] 的字符频次。只有代码的初始化、更新顺序和终止条件都维持它，样例通过才具有证明力。

典型路径从“s=“cbaebabacd”, p=“abc”, m=3”开始手推，最后应得到“结果 [0,6]”。
边界复核：p.length()>s.length() 时没有窗口；若字符集不限小写字母，应换 Map 或扩大计数结构。
代价复核：数组整体比较写法是 O(Σn)，小写字母 Σ=26 可视为 O(n)；差异计数可严格常数判断。
用空串、单字符、全相同字符和首尾命中检查下标边界。
涉及窗口或双指针时，明确区间是闭区间还是左闭右开，并在移动后再判断长度。
涉及计数数组时，先确认题目字符集；超出小写英文字母就不能硬套 26 个桶。

最后要主动构造一个“少写一次循环、改变一个不等号或交换两行更新就会失败”的反例。能说清反例破坏了哪条不变量，比只报出复杂度更能证明真正掌握了算法。

记忆钩子：本题的代码可以压缩，但“检查答案时窗口长度恒为 m，窗口计数恰好等于 s[left..right] 的字符频次。”这条正确性主线不能省。

八、常见误区与追问

误区：窗口长度可以动态伸缩。 异位词必须与 p 等长，固定窗口更直接，动态窗口反而增加状态。
误区：字符集合相同就一定是异位词。 频次也必须相同，例如 aab 与 abb 的集合相同但不是异位词。
误区：每个窗口重新排序仍是线性时间。 长度 m 的排序需要 O(m log m)，总成本明显更高。
追问：如何把每次比较 26 个计数优化成 O(1)？ 维护不匹配字符种类数或 matched 计数，进出窗口时只更新受影响字符。
追问：结果为什么记录 left 而不是 right？ 窗口表示 [right-m+1,right]，其起点就是维护后的 left。
追问：若允许 Unicode 怎么办？ 不能假设 26 个小写字母，应按码点使用哈希映射并正确遍历码点。

九、加强记忆

找所有字母异位词子串 = 固定宽度（= p.length()）滑动窗口 + 计数比较。窗口在 s 上滑动，右端 window[s[i]]++、当 i>=n 时左端 window[s[i-n]]-- 保持定宽；当 i>=n-1 且 window == need（p 的字母计数），记录起点 i-n+1。异位词长度固定 ⇒ 用定长窗口（对比最小覆盖子串/无重复子串的变长窗口）。判等可用 Arrays.equals（O(26n)）或维护 matched 种类数（O(n)）。核心：定长窗口滑一遍，频次相等就记起点。

简化版

详细版