题目：
给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
示例 1:
输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。
示例 2:
输入: s = "abab", p = "ab"
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。
核心问题
字母异位词要求：每个字符的出现次数完全相同
核心思想就一句话：字母异位词 = 每个字母出现的次数完全相同。
为什么不能只判断"字母存在"？
p = "aab"
错误判断: "aaa" 也是异位词
原因: a 存在 ✓, a 存在 ✓, a 存在 ✓
但实际上 p 里只有 2 个 a，不是 3 个！
正确判断: 必须检查频率
p: a 出现 2 次, b 出现 1 次
"aaa": a 出现 3 次, b 出现 0 次 ✗ 不匹配
"aba": a 出现 2 次, b 出现 1 次 ✓ 匹配！
如何判断频率相同？
用字符计数数组：
p = "abc"
pCount = [1, 1, 1, 0, 0, …, 0]
a b c d e z
对于 s 中的每个长度为 3 的窗口，也统计一个 sCount，然后对比：
s = "cbaebabacd"
窗口 "cba":
sCount = [1, 1, 1, 0, …] ✓ 和 pCount 完全一样！
a b c
窗口 "bae":
sCount = [1, 1, 0, 0, 1, …] ✗ c=0, e=1，不匹配
a b c d e
滑动窗口怎么更新计数？
不需要每次都重新统计整个窗口，只需要：
窗口右移 = 加入右边的新字符 + 移除左边的旧字符
"cba" → "bae"
↑删除 ↑新增
操作:
sCount[c]– (移除 c)
sCount[e]++ (加入 e)
完整过程演示
s = "cbaebabacd", p = "abc"
pCount: [1,1,1,0,0,…,0]
a b c
i=0: 加入c → sCount:[0,0,1,0,0,…]
i=1: 加入b → sCount:[0,1,1,0,0,…]
i=2: 加入a → sCount:[1,1,1,0,0,…] ✓ 匹配！记录索引0
i=3: 加入e, 移除c → sCount:[1,1,0,0,1,…] ✗
i=4: 加入b, 移除b → sCount:[1,1,0,0,1,…] ✗
i=5: 加入a, 移除a → sCount:[1,1,0,0,1,…] ✗
…
本质
这是滑动窗口 + 固定长度 + 频率统计的组合：
题解一
class Solution {
public List<Integer> findAnagrams(String s, String p) {
List<Integer> result = new ArrayList<>();
if (s.length() < p.length()) return result;
int[] pCount = new int[26];
int[] sCount = new int[26];
for (char c : p.toCharArray()) {
pCount[c – 'a']++;
}
for (int i = 0; i < s.length(); i++) {
sCount[s.charAt(i) – 'a']++;
if (i >= p.length()) {
sCount[s.charAt(i – p.length()) – 'a']–;
}
if (Arrays.equals(pCount, sCount)) {
result.add(i – p.length() + 1);
}
}
return result;
}
}
缺点：这个方法时间复杂度是 O(n×m)，会很慢，运行大概率超时。
题解二
class Solution {
public List<Integer> findAnagrams(String s, String p) {
List<Integer> result = new ArrayList<>();
if (s.length() < p.length()) return result;
int[] pCount = new int[26];
int[] sCount = new int[26];
for (char c : p.toCharArray()) {
pCount[c – 'a']++;
}
for (int i = 0; i < s.length(); i++) {
sCount[s.charAt(i) – 'a']++;
if (i >= p.length()) {
sCount[s.charAt(i – p.length()) – 'a']–;
}
if (Arrays.equals(pCount, sCount)) {
result.add(i – p.length() + 1);
}
}
return result;
}
}
核心技巧
这段代码巧妙在只用一次遍历就维护了滑动窗口：
- 不需要嵌套循环重新统计窗口
- 每次只做 +1 和 -1 操作，效率极高
- 时间复杂度 O(n)，空间复杂度 O(1)
if (Arrays.equals(pCount, sCount)) {
result.add(i – p.length() + 1);
}
```
**检查当前窗口是否匹配**。
– `Arrays.equals(pCount, sCount)` 比较两个数组是否完全相等
– 如果相等，说明当前窗口是字母异位词
– `i – p.length() + 1` 计算**窗口的起始索引**
**为什么是 `i – p.length() + 1`？**
– 窗口右边界是 `i`
– 窗口长度是 `p.length()`
– 所以左边界是 `i – p.length() + 1`
举例：`i = 4`, `p.length() = 3`，窗口是 `[2, 3, 4]`，起始索引是 `4 – 3 + 1 = 2`
## 完整演示
```
s = "cbaebabacd", p = "abc" (长度3)
pCount = [1, 1, 1, 0, 0, …, 0]
a b c
i=0: 加入 s[0]='c'
sCount = [0,0,1,0,0,…]
窗口长度=1 < 3，不移除
不匹配
i=1: 加入 s[1]='b'
sCount = [0,1,1,0,0,…]
窗口长度=2 < 3，不移除
不匹配
i=2: 加入 s[2]='a'
sCount = [1,1,1,0,0,…]
窗口长度=3，不移除 (i=2 < p.length()=3)
匹配！ → 添加 2-3+1=0
i=3: 加入 s[3]='e'
sCount = [1,1,1,0,1,…]
i=3 >= p.length()=3，移除 s[3-3]='c'
sCount = [1,1,0,0,1,…]
不匹配
i=4: 加入 s[4]='b'
sCount = [1,2,0,0,1,…]
移除 s[4-3]=s[1]='b'
sCount = [1,1,0,0,1,…]
不匹配
…以此类推
