给定两个字符串 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" 的异位词。
提示:
1 <= s.length, p.length <= 3 * 104
s 和 p 仅包含小写字母
滑动窗口算法的思路是维护一个窗口，不断滑动，然后更新答案。
该算法的大致逻辑如下：
int left = 0, right = 0;
while (right < s.size()) {
// 增大窗口
window.add(s[right]);
right++;
while (window needs shrink) {
// 缩小窗口
window.remove(s[left]);
left++;
}
}
这个算法的时间复杂度是 O(N)，比暴力字符串算法高效得多。
滑动窗口算法代码的框架如下：
/* 滑动窗口算法框架 */
void slidingWindow(string s, string t) {
unordered_map<char, int> need, window;
for (char c : t) need[c]++;
int left = 0, right = 0;
int valid = 0;
while (right < s.size()) {
// c 是将移入窗口的字符
char c = s[right];
// 增大窗口
right++;
// 进行窗口内数据的一系列更新
...
/*** debug 输出的位置 ***/
printf("window: [%d, %d)\n", left, right);
/********************/
// 判断左侧窗口是否要收缩
while (window needs shrink) {
// d 是将移出窗口的字符
char d = s[left];
// 缩小窗口
left++;
// 进行窗口内数据的一系列更新
...
}
}
}
我们需要关注的是如何向窗口中添加元素，如何缩小窗口，在窗口滑动的哪个阶段更新结果。
func findAnagrams(s string, p string) []int {
window := make(map[byte]int)
need := make(map[byte]int)
pLen := len(p)
for i := 0; i < pLen; i++ {
need[p[i]]++
}
left, right := 0, 0
valid := 0
var res []int
for right < len(s) {
c := s[right]
right++
// 更新滑动窗口数据
if _, ok := need[c]; ok {
window[c]++
if window[c] == need[c] {
valid++
}
}
// 收缩窗口
for (right - left) >= pLen {
if valid == len(need) { // 有满足条件的子串
res = append(res, left)
}
d := s[left]
left++
if _, ok := need[d]; ok {
if window[d] == need[d] {
valid--
}
window[d]--
}
}
}
return res
}