中等LeetCode 438可逐步演示引导学习
找到字符串中所有字母异位词
固定窗口：窗口内的字符账本
维护长度等于 p 的固定窗口，统计窗口内和 p 的字符频次；两者完全一致时，窗口起点就是一个答案。
时间复杂度 O(n)（字母表固定）空间复杂度 O(1)
题单：面试热题
题目描述
给定两个字符串 s 和 p，找出 s 中所有 p 的字母异位词的起始下标。字母异位词指字母种类和数量相同、顺序不同的字符串。
学习目标
说清固定窗口为什么适合异位词，独立写出字符频次滑动窗口。
已完成 0 / 6 阶段
诊断
异位词看什么
两个字符串互为异位词，要比什么？
比较异位词最直接看？
建议先完成当前阶段（提示 / 检查 / 自评），再进入下一步；也可以直接跳过。
解题思路
核心思想
维护长度等于 p 的固定窗口，统计窗口内和 p 的字符频次；两者完全一致时，窗口起点就是一个答案。
为什么需要它
每个起点重新统计窗口字符最坏 O(n·m)；固定窗口滑动时只进一个字符、出一个字符，频次表可以 O(1) 更新。
第一反应：直觉方案
枚举每个长度 m 的子串，排序后和 p 比较；能工作，但重复排序和重复计数太多。
关键洞察
异位词只关心字符出现次数，不关心顺序；p 长度固定，窗口长度也固定，滑动一步只改变两个计数，可以增量维护频次。
时间复杂度 O(n)（字母表固定）空间复杂度 O(1)
易错点
- 窗口长度固定为 p.length，p 更长直接返回空数组。
- 先加入右端，再移除左侧超出字符，顺序不要反。
- 固定 26 数组只适合小写字母。
逐步演示
参考代码
1function findAnagrams(s, p) {
2 const result = [];
3 const m = p.length;
4 if (m > s.length) return result;
5 const need = new Array(26).fill(0);
6 const window = new Array(26).fill(0);
7 const base = 'a'.charCodeAt(0);
8 for (const ch of p) need[ch.charCodeAt(0) - base]++;
9 const same = () => {
10 for (let i = 0; i < 26; i++) {
11 if (need[i] !== window[i]) return false;
12 }
13 return true;
14 };
15 for (let i = 0; i < s.length; i++) {
16 window[s.charCodeAt(i) - base]++;
17 if (i >= m) window[s.charCodeAt(i - m) - base]--;
18 if (i >= m - 1 && same()) result.push(i - m + 1);
19 }
20 return result;
21}
效果图
当前场景
need
a: 1b: 1c: 1
window
第 1 / 15 步