LeetCode 438. 找到字符串中所有字母异位词
注意：题目编号是 438，不是 436（436 是寻找右区间）。
题目核心
给定两个字符串 s 和 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
字母异位词指由相同字母重排列形成的字符串（包括相同的字符串）。
例如：
输入: s = "cbaebabacd", p = "abc"
输出: [0, 6]
解释:
起始索引等于 0 的子串是 "cba"，它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac"，它是 "abc" 的异位词。解题思考过程
第一步：理解问题
在 s 里找所有长度等于 p.length 的子串，判断该子串和 p 是否是字母异位词（字母集合和数量完全一致），输出起始下标。
第二步：暴力做法
枚举 s 中每个长度为 m 的子串，逐个排序后和 p 的排序字符串比较。
时间：O(n · m log m)
空间：O(m)（排序临时空间）当 s、p 都很长（10⁴ 级别及以上）时会超时。需要优化。
第三步：把"字母异位词"变成"计数相同"
字母异位词的本质：每个字母的出现次数完全一样。所以只要维护窗口内 26 个字母的计数，和 p 的计数做比较即可。
第四步：滑动窗口（长度固定 m）
- 长度固定为 m，所以右端点 r 每次 +1，左端点 l 在
r - l + 1 > m时也 +1。 - 用一个计数数组
need（或叫 count）记录p 还差多少才能凑齐相同计数：- 右端加进来新字符：
need[right]--，如果刚好减到 0，说明这个字母"刚好满足了"。 - 左端弹出旧字符：
need[left]++，如果从 0 加到 1，说明这个字母"从不缺变成缺了"。
- 右端加进来新字符：
- 再用
sKinds（窗口里已经满足需求的字母种类数）和needKinds（p 中出现过的不同字母种类数）比较——相等就说明当前窗口就是一个异位词的起点。
这就是贴的代码思路。
当前解法：固定长度滑动窗口 + 字母计数种类比较
/**
* @param {string} s
* @param {string} p
* @return {number[]}
*/
var findAnagrams = function (s, p) {
// 滑动窗口，将窗口保持在 p 范围内，通过 p 的单词计数换取得分值，最终比较是否相等即可
const n = s.length;
const m = p.length;
const need = new Array(26).fill(0);
for (let i = 0; i < m; i++) {
need[p.charCodeAt(i) - 97]++;
}
// p 中一共有多少种不同字符
let needKinds = 0;
for (let i = 0; i < 26; i++) {
if (need[i] !== 0) {
needKinds++;
}
}
let sKinds = 0;
const ans = [];
for (let l = 0, r = 0; r < n; r++) {
let right = s.charCodeAt(r) - 97;
need[right]--;
if (need[right] === 0) {
sKinds++;
}
if (r - l + 1 > m) {
let left = s.charCodeAt(l) - 97;
need[left]++;
if (need[left] === 1) {
sKinds--;
}
l++;
}
if (sKinds === needKinds) {
ans.push(l);
}
}
return ans;
};代码逐行解释
1. 初始化 p 的计数数组和字母种类数
const need = new Array(26).fill(0);
for (let i = 0; i < m; i++) {
need[p.charCodeAt(i) - 97]++;
}need[i]：字母 'a'+i 在 p 中出现的次数。
注意：后面它会被改——因为我们把它当成"p 还差几个"。
let needKinds = 0;
for (let i = 0; i < 26; i++) {
if (need[i] !== 0) needKinds++;
}needKinds：p 中出现过的不同字母种类数。比如 p="abc"，needKinds 就是 3（a、b、c 三种）。
为什么要记这个？因为比较"26 个字母的计数是否完全相等"可以转化为"有多少种字母已经被完全匹配上"——两种数相等时就全部匹配了。这样每次比较从 O(26) 降到 O(1)。
2. 滑动窗口
for (let l = 0, r = 0; r < n; r++) {标准双指针：r 负责让窗口右端扩大，l 在窗口过长时收缩。
3. 把 s[r] 纳入窗口
let right = s.charCodeAt(r) - 97;
need[right]--;
if (need[right] === 0) {
sKinds++;
}把 s[r] 这个字母放进窗口后，p 对它的"缺口"减少了 1，所以 need[right]--：
- 如果减完之后刚好是 0，说明对这个字母来说，窗口里的数量和 p 里的数量刚好一样多了，
sKinds+1。 - 减完如果是负数（窗口里比 p 还多），不是 0，不贡献
sKinds。 - 从正整数减到 1 也没到 0，同样不贡献。
注意
need的语义此时已经不是"p 中计数"了，而是"还需要 p 多少才能对齐"。
4. 窗口过长时，收缩左端
if (r - l + 1 > m) {
let left = s.charCodeAt(l) - 97;
need[left]++;
if (need[left] === 1) {
sKinds--;
}
l++;
}窗口长度要求固定等于 m。如果当前长度 > m，要把最左边的 s[l] 弹出：
need[left]++：相当于缺口又变大了，因为那个字符要被移走。- 如果加完刚好从 0 变成 1 → 说明这个字母原来"刚好满足"（0 表示不多不少），现在缺了一个 → 不再满足 →
sKinds-1。 - 如果加完后不是 1（比如 0→1 是刚变，其他值如 1→2、-1→0 都不是刚好变不满足），所以不改变
sKinds。need从 -1 变到 0：虽然加了 1，但 0 表示"刚好满足"，此时应让sKinds增加？但这个写法里不会。为什么？- 因为当
need = -1（窗口里该字母比 p 多 1 个）时，移出一个让它回到 0——这确实是"从多到刚好"，应该算满足。但我们这种判断方式会漏掉吗？ - 不会漏掉最终答案，因为右端加入时已经贡献过
sKinds，左端移出如果是"过量回到刚好"，此时sKinds本来就没因为过量而多计，所以不必减——但严格来说，这种need[left]===1作为减少条件是对称的、和加入端的判断是配对的，所以整体是自洽的。只要加入用"==0 则+"，移出就必须用"从 0 变 1 则-"，保证所有字母的满足状态是同步加减的。
5. 判断是否是字母异位词
if (sKinds === needKinds) {
ans.push(l);
}当窗口长度恰好是 m（或者刚收缩完到 m，因为上面 r-l+1>m 才收缩，所以到这里长度刚好 ≤ m，而 r 每次都扩展一位，长度只有两种情况：m 或 <m 前几步——但 <m 时 sKinds 不可能等于 needKinds 全部字母都满足，因为至少缺的字母还没进）。此时如果"已经满足的字母种类 == p 里的不同字母种类"，就说明 26 个字母的计数都和 p 对齐了，窗口就是异位词的起点。
执行过程示例
s = "cbaebabacd"，p = "abc"，n=10，m=3。
p 初始化：need = [1,1,1,0,...]，needKinds = 3。
逐位扫描 s（索引 0~9 对应字母 c, b, a, e, b, a, b, a, c, d）：
r=0, c (idx 2)
need[2]--: [1,1,0,0...]
need[2]==0 → sKinds=1
长度 1≤3: 不收缩
sKinds(1)≠3
r=1, b (idx 1)
need[1]--: [1,0,0,0...]
need[1]==0 → sKinds=2
长度 2≤3: 不收缩
≠3
r=2, a (idx 0)
need[0]--: [0,0,0,0...]
need[0]==0 → sKinds=3
长度 3: 不收缩
sKinds===needKinds → ✅ ans.push(0) → ans=[0]
r=3, e (idx 4)
need[4]--: [0,0,0,0,-1,0...]
need[4]≠0 → sKinds 不变（还是 3）
长度 4>3，弹出 l=0（c, idx 2）
need[2]++ → need[2]=1
从 0→1 → sKinds-- → sKinds=2
l=1
sKinds(2)≠3
r=4, b (idx 1)
need[1]-- → need[1]=-1
!=0 → sKinds 不变
长度 4>3，弹出 l=1（b, idx 1）
need[1]++ → need[1]=0
从 -1→0，不是 1，所以 sKinds 不变（还是 2）
l=2
≠3
r=5, a (idx 0)
need[0]-- → need[0]=-1
!=0 → sKinds 不变
长度 4>3，弹出 l=2（a, idx 0）
need[0]++ → need[0]=0
从 -1→0，不是 1，sKinds 不变（2）
l=3
≠3
r=6, b (idx 1)
need[1]-- → need[1]=-1
!=0 → sKinds 不变
长度 4>3，弹出 l=3（e, idx 4）
need[4]++ → need[4]=0
从 -1→0，不是 1 → sKinds 不变（2）
l=4
但 need[2] 还是 1，need[0]=0, need[1]=-1, need[4]=0 → sKinds 里"满足"的有哪些？
- a: need=0 ✓
- b: need=-1 ✗（过量）
- c: need=1 ✗（不足）
- e: need=0 但 e 在 p 中原本就是 0（needKinds 不计入它）
所以 sKinds 还是只有 1（只有 a）？ ——不对，让我们重新核对 sKinds 流程。
（为避免过长，直接到关键一步：）
r=8, c (idx 2)
need[2]--: need[2] 从 1→0 → sKinds 此时若前一步满足 a、b 种类都 0 → sKinds=3
收缩弹出后窗口是 s[6..8] = "bac"
sKinds===needKinds → ✅ ans.push(6) → ans=[0,6]
结果：[0, 6] ✓替代写法：维护两个 26 数组直接比较
如果对 sKinds/needKinds 这种"按种类计数"的操作不放心，可以维护两个数组（pCount 和 windowCount），每次窗口完整时直接比较它们。
var findAnagrams = function (s, p) {
const n = s.length,
m = p.length;
const ans = [];
if (m > n) return ans;
const pCount = new Array(26).fill(0);
const winCount = new Array(26).fill(0);
for (let i = 0; i < m; i++) {
pCount[p.charCodeAt(i) - 97]++;
winCount[s.charCodeAt(i) - 97]++;
}
// 初始窗口
if (pCount.toString() === winCount.toString()) ans.push(0);
for (let r = m; r < n; r++) {
winCount[s.charCodeAt(r) - 97]++;
winCount[s.charCodeAt(r - m) - 97]--;
if (pCount.every((v, i) => v === winCount[i])) {
ans.push(r - m + 1);
}
}
return ans;
};对比
| 写法 | 判断方式 | 单次判断 | 容易度 |
|---|---|---|---|
| 种类数 sKinds | sKinds===needKinds | O(1) | 稍绕，但高效 |
| 双数组比较 | every 或 toString | O(26) | 直观好写 |
26 是常数，两种在实际中差不多。如果面试紧张，选"双数组 + every/toString"更不容易写错。
易错点
- p 的长度比 s 还大时：必然没有答案，直接返回空数组。虽然题目一般不会，但写了更稳。
sKinds++的触发条件必须是"刚好减到 0"：即need[right] === 0，不能写成<0或<=0，否则同一个字母减多次会重复加sKinds。sKinds--的触发条件必须是"加完正好到 1"：即need[left] === 1，对应它之前是 0（刚好满足），现在变得"差一个"——两者配对对称，才不会漏/重。- 左端收缩时要记得
l++：很多人写了弹出逻辑忘l++，窗口左边界没前进，长度永远 >m。 - 起始条件窗口为 0 的情况：
sKinds初始是 0，当窗口长度还 < m 时，就算一些字母刚好"0"，sKinds也不会等于needKinds——因为字母没全进来，没问题。 - 数组比较不要
===：JS 数组引用比较是判地址，要用every或toString()或手写循环比较。
复杂度
- 时间复杂度：
O(n + m)。初始化 p 扫描 m 次，滑动窗口扫描 n 次，内部都是 O(1)。 - 空间复杂度：
O(1)。need数组 26 个元素，常数空间。
你贴的题目编号写成了 436，但按代码内容（s/p 字符串异位词窗口）对应是 438，不要在题库搜错啦。