问题描述
给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。
提示:
1 <= s.length, p.length <= 3 * 10^4s和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" 的异位词。
解题思路
根据题目要求，我们需要在字符串 s 寻找字符串 p 的异位词。因为字符串 p 的异位词的长度一定与字符串 p 的长度相同，所以我们可以在字符串 s 中构造一个长度为与字符串 p 的长度相同的滑动窗口，并在滑动中维护窗口中每种字母的数量；当窗口中每种字母的数量与字符串 p 中每种字母的数量相同时，则说明当前窗口为字符串 p 的异位词。
具体来说，我们用一个 map 统计 p 中每个字母出现的次数，然后滑动窗口内每个字母都要出现在 p 中，且个数不超过 p 中相应字母的个数。我们在遍历的时候主要会遇到以下情况。
字符可以添加进滑动窗口
如果 s[i] 出现在 p 中，且滑动窗口内 s[i] 的个数小于 p 中相应字符的个数，则可以将 s[i] 添加进滑动窗口。
字符出现在 p 内，但滑动窗口内该字符已满
此时，我们假设 s[i'] == s[i] ，i' 是滑动窗口内字符 s[i] 第一次出现时在 s 中的下标。我们将 i' 及 i' 之前的元素从滑动窗口中弹出，并将 s[i] 添加进滑动窗口，此时还要根据弹出的元素数量更新当前滑动窗口内元素的数量。
字符不在 p 内
此时，应该将滑动窗口的起始位置放在 i + 1 处，并将滑动窗口内的元素全部弹出。
根据上述分析，实现如下代码：
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
if(s.size() < p.size()){ // 如果s的长度小于p的长度，直接返回空
return {};
}
vector<int> res;
map<char, int> cnt; // 记录每个单词的频率
for(int i = 0; i < p.size(); i++){
cnt[p[i]]++;
}
int windowSize = p.size();
int cursor = 0;
for(int i = 0; i <= s.size(); i++){ // 通过滑动窗口遍历s
for(int j = i + cursor; j < s.size() && cursor < windowSize; j++){ // cursor指向滑动窗口内下一个元素的位置
if(cnt.count(s[j])){ // 判断s[j]是否出现在p内
if(cnt[s[j]]){ // s[j]在p内，且还可以再添加进滑动窗口
cnt[s[j]]--;
cursor++;
if(cursor == windowSize){ // 判断滑动窗口是否已满
res.push_back(i); // 添加结果
cnt[s[i]]++; // 将滑动窗口底部元素弹出
cursor--;
break;
}
}
else{ // 滑动窗口内已有足够多的该元素
int k = i;
for(; s[k] != s[j]; k++){ // 将该元素及该元素以前的元素一起弹出滑动窗口
cnt[s[k]]++;
cursor--;
}
i = k;
break;
}
}
else{ // s[j]未出现在p内
for(int k = i; k < j; k++){ // 将j之前的元素弹出
cnt[s[k]]++;
}
i = j;
cursor = 0;
break;
}
}
}
return res;
}
};