找到字符串中所有字母異位詞
題目描述：
????????給定兩個字符串?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" 的異位詞。
思路分析：
依然是滑動窗口法
????????根據題目要求，我們需要在字符串 s尋找字符串 p?的異位詞。因為字符串 p?的異位詞的長度一定與字符串 p的長度相同，所以我們可以在字符串 s中構造一個長度為與字符串 p?的長度相同的滑動窗口，并在滑動中維護窗口中每種字母的數量；當窗口中每種字母的數量與字符串 p?中每種字母的數量相同時，則說明當前窗口為字符串 p?的異位詞。
優化思路
????????在上述方法的基礎上，我們不再分別統計滑動窗口和字符串中每種字母的數量，而是統計滑動窗口和字符串 p中每種字母數量的差；并引入變量cnt來記錄當前窗口與字符串 p中數量不同的字母的個數，并在滑動窗口的過程中維護它。
????????在判斷滑動窗口中每種字母的數量與字符串 p中每種字母的數量是否相同時，只需要判斷cnt是否為零即可。
代碼實現注解：
class Solution {public List<Integer> findAnagrams(String s, String p) {List<Integer>res=new ArrayList<>();//定義一個一維數組記錄字母在兩個字符串中出現的差值//cnt[x] = 0 表示 s與p中字母x出現次數相同 都出現了n次//cnt[x] = n 表示 在s中字母x出現次數比p多 多出現了n次//cnt[x] = -n 表示 在s中字母x出現次數比p少 少出現了n次int[]cnt=new int[26];//統計字符數量int n=p.length();int m=s.length();//如果目標字符長度大于原始字符長度，返回空數組if(n>m){return res;}//開始遍歷數組，創造窗口滑塊，p數組出現的字母數值加一，S數組出現的字母數字減一。//所以當cnt數組上的數值為0是代表在滑塊中p和s出現該字母的頻率一致for(int i=0;i<n-1;i++){cnt[p.charAt(i)-'a']++;cnt[s.charAt(i)-'a']--;}//將P字符串中的最后一個字母讀入cnt中cnt[p.charAt(n-1)-'a']++;int l=0;//將S字符串中的n-1位置上的字母作為滑塊的右邊界//開始滑動窗口for(int r=n-1;r<m;r++){cnt[s.charAt(r)-'a']--;int o=0;//隨著右邊界的右移，判斷新的右邊界。如果cnt數組上的數值為0，那么o賦值為1for(int j=0;j<26;j++){o+=cnt[j]==0?1:0;}//說明s和p的同一個字母出現頻率相等if(o==26){res.add(l);}//左邊界向右移，縮小窗口cnt[s.charAt(l++)-'a']++;}return res;}
}
)
