給定兩個字符串?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?僅包含小寫字母

方法一：滑動窗口
思路

根據題目要求，我們需要在字符串 s 尋找字符串 p 的異位詞。因為字符串 p 的異位詞的長度一定與字符串 p 的長度相同，所以我們可以在字符串 s 中構造一個長度為與字符串 p 的長度相同的滑動窗口，并在滑動中維護窗口中每種字母的數量；當窗口中每種字母的數量與字符串 p 中每種字母的數量相同時，則說明當前窗口為字符串 p 的異位詞。

算法

在算法的實現中，我們可以使用數組來存儲字符串 p 和滑動窗口中每種字母的數量。

細節

當字符串 s 的長度小于字符串 p 的長度時，字符串 s 中一定不存在字符串 p 的異位詞。但是因為字符串 s 中無法構造長度與字符串 p 的長度相同的窗口，所以這種情況需要單獨處理。

代碼

class Solution {
public:vector<int> findAnagrams(string s, string p) {int sLen = s.size(),pLen = p.size();if(sLen < pLen){return vector<int>();}vector<int> sCount(26);vector<int> pCount(26);vector<int> ans;for(int i = 0; i < pLen;i ++){++sCount[s[i] - 'a'];++pCount[p[i] - 'a'];}if(sCount == pCount){ans.emplace_back(0);}for(int i = 0; i < sLen - pLen; ++i){--sCount[s[i] - 'a'];++sCount[s[i+pLen] - 'a'];if(sCount == pCount){ans.emplace_back(i + 1);}}return ans;}
};