滑动窗口—找到字符串中所有字母异位词

异位词：字母种类、个数相同
要求：在s里找到所有和p是异位词的子串，返回它们的起始下标

例子：
s = "cbaebabacd", p = "abc"
异位词子串：cba（下标 0）、bac（下标 6）
输出：[0,6]

最优思路（滑动窗口+计数）
1、固定窗口大小：窗口长度=p的长度
2、计数数组：用2个大小为26的数组（因为字母有26个），分别统计p和当前窗口s的字母数量
3、滑动：窗口从左向右滑，每次滑一步，比较两个计数数组
相等 ——> 是异位词，记录起始下标

完整代码实现如下：
#include
#include
#include
using namespace std;

vector findAnagrams(string s, string p) {
vector res; // 存储结果下标
vector count_s(26); // 统计s窗口内字母数量
vector count_p(26); // 统计p字母数量
int len_s = s.size();
int len_p = p.size();

// 1. 先统计p的字母数量
for (char ch : p) {count_p[ch - 'a']++;
}// 2. 滑动窗口遍历s
for (int right = 0; right < len_s; right++) {// 把右指针字符加入窗口count_s[s[right] - 'a']++;// 窗口超过p长度 → 移除左指针字符（收缩窗口）if (right >= len_p) {count_s[s[right - len_p] - 'a']--;}// 窗口大小等于p长度 → 比较是否是异位词if (right >= len_p - 1) {if (count_s == count_p) {// 起始下标 = right - len_p + 1res.push_back(right - len_p + 1);}}
}
return res;

}

// 测试
int main() {
string s = "cbaebabacd";
string p = "abc";
vector ans = findAnagrams(s, p);

// 输出结果：0 6
for (int idx : ans) {cout << idx << " ";
}
return 0;

}

代码逐行解释：
1、统计字符数量

• 用ch-'a' 把字母转成0~25的数字
• count_p记录p窗口每个字母出现多少次

2、滑动窗口核心：

• 右指针：一直往右走，把s字符串中的字符加入s窗口
• 窗口超界：right>=len_p时，移除最左边的字符（right是下标，right==len_p也代表窗口的长度超过了len_p,）
• 窗口匹配长度：right >= len_p -1时，窗口大小刚好等于p时开始比较count_s和count_p
  相等 -> 是异位词，把s窗口的起始下标(right - len_p +1)加入结果

3、起始下标计算
起始下标 = right -len_p + 1
right -len_p 刚好是窗口外的那个元素，因此需要right -len_p + 1才等于窗口内的起始字符下标
count_s[s[right - len_p] - 'a']--;移除左指针元素的时候，不需要加1，因为此时right-len_p就是窗口外需要删除的那个字符

复杂度：
时间O（n） ：n是s长度，一次遍历
空间O（1） : 只用了2个固定大小26的数组

总结：
固定窗口：大小 = p 的长度
计数比较：窗口字符计数 == p 字符计数
滑动：右进左出，一次遍历

这题和上一题滑动窗口思想完全一致，只是从「可变窗口」变成了「固定窗口」！