這道題主要是利用"窗口"這一概念，優化的時候可以利用題目本身的特殊性。
原題
給定一個字符串 s 和一個非空字符串 p，找到 s 中所有是 p 的字母異位詞的子串，返回這些子串的起始索引。
字符串只包含小寫英文字母，並且字符串 s 和 p 的長度都不超過 20100。
說明：
- 字母異位詞指字母相同，但排列不同的字符串。
- 不考慮答案輸出的順序。
示例 1:
<code>輸入:s: "cbaebabacd" p: "abc"輸出:[0, 6]解釋:起始索引等於 0 的子串是 "cba", 它是 "abc" 的字母異位詞。起始索引等於 6 的子串是 "bac", 它是 "abc" 的字母異位詞。/<code>
示例 2:
<code>輸入:s: "abab" p: "ab"輸出:[0, 1, 2]解釋:起始索引等於 0 的子串是 "ab", 它是 "ab" 的字母異位詞。起始索引等於 1 的子串是 "ba", 它是 "ab" 的字母異位詞。起始索引等於 2 的子串是 "ab", 它是 "ab" 的字母異位詞。/<code>
原題url：https://leetcode-cn.com/problems/find-all-anagrams-in-a-string/
解題
利用"窗口"思想
這道題類似字符串完全匹配，只是這道題要求連續但順序可以不一致。這樣就無法利用待匹配字符串預先構造了。
那麼結合這道題，為了能夠讓我們知道當前字符是否在待匹配字符串中，我們需要一個集合存儲。
為了能夠讓我們知道各個字符出現了幾次，我們需要一個哈希表，並且實時更新其次數，如果次數為0，則移除該項，如果哈希表為空，則說明找到了，記錄開始下標，並且窗口滑動。
結合上面的思路，我們可以寫出代碼：
<code>class Solution { public List<integer> findAnagrams(String s, String p) { // 最終結果 List<integer> result = new LinkedList<>(); if (s == null || s.length() == 0) { return result; } // 根據p構造map，key代表字符，value代表相應次數 Map<character> map = new HashMap<>(); for (Character character : p.toCharArray()) { map.put(character, map.getOrDefault(character, 0) + 1); } // p中所有的字符 Set<character> pCharSet = new HashSet<>(map.keySet()); // 每個字母出現的位置，value表示每一次出現的下標 Map<character>> indexMap = new HashMap<>(); // 開始的下標 int first = 0; char[] sArray = s.toCharArray(); // 遍歷s for (int i = 0; i < sArray.length; i++) { Character character = sArray[i]; // 如果character不在pCharSet中，說明該字符不存在 if (!pCharSet.contains(character)) { // 則重新構造indexMap indexMap = new HashMap<>(); // 從first位置到i位置，還原map for (int j = first; j < i; j++) { character = sArray[j]; map.put(character, map.getOrDefault(character, 0) + 1); } // 重置first的位置 first = i + 1; continue; } // 從indexMap中獲取該字符出現的位置 LinkedList<integer> indexList = indexMap.computeIfAbsent(character, k -> new LinkedList<>()); // 在末尾記錄當前位置 indexList.add(i); // map中相應字符剩餘出現次數 Integer count = map.get(character); // 如果次數為null，說明無法再減 if (count == null) { // 從開始下標到該字符第一次出現的下標，還原map和indexMap int firstIndex = indexList.removeFirst(); for (int j = first; j < firstIndex; j++) { character = sArray[j]; map.put(character, map.getOrDefault(character, 0) + 1); indexMap.get(character).removeFirst(); } // 重置first的位置 first = firstIndex + 1; continue; } // 次數-1 count--; // 如果次數不為0，則重新放進map中 if (count > 0) { map.put(character, count); continue; } // 如果次數減為0，則移除該項 map.remove(character); // 檢查map是否為空 if (!map.isEmpty()) { continue; } // 如果為空，說明滿足條件，記錄進result中 result.add(first); // first向後移動1個（窗口滑動） character = sArray[first]; map.put(character, map.getOrDefault(character, 0) + 1); indexMap.get(character).removeFirst(); first++; } return result; }}/<integer>/<character>/<character>/<character>/<integer>/<integer>/<code> 提交OK，但執行用時很慢，需要優化。
優化
上面解法查詢慢，我感覺根本原因在於使用了比較複雜的數據結構，包括集合、哈希表、鏈表等，雖然 Java 中針對這些結構做了優化，但相比於最基礎的結構數組而言，在查找和更新上還是更慢了。這道題可以用數組的主要原因在於只會出現26個小寫英文字母。這樣用了數組之後，查找和更新都快了太多。大家可以根據這個思路優化試試。
既然有提到窗口，那麼我們就將這個思想用到極致。可以先將窗口設置的大一些，比如至少包含目標字符串裡的所有字符。達成條件後，就開始把左邊開始縮小，直到縮小成目標字符串的長度後，然後記錄進結果中，之後窗口右移，重複上述過程。
接下來看看代碼：
<code>class Solution { public List<integer> findAnagrams(String s, String p) { if(s == null || s.length() == 0) return new ArrayList<>(); List<integer> res = new ArrayList<>(); // 需要的字符，由於都是小寫字母，因此直接用26個長度的數組代替原來的HashMap int[] needs = new int[26]; for(char ch : p.toCharArray()) { needs[ch - 'a'] ++; } // "窗口" int[] window = new int[26]; // 窗口的左右下標 int left = 0, right = 0; // 用total檢測窗口中是否已經涵蓋了p中的所有字符 int total = p.length(); // 遍歷s while(right < s.length()) { char chr = s.charAt(right); // 如果該字符在p中出現過 if(needs[chr - 'a'] > 0) { // 則在窗口中記下該字符 window[chr - 'a'] ++; // 如果當前窗口中該字符的數量，小於需要的數量 if(window[chr - 'a'] <= needs[chr - 'a']) { // 則total數量減1 total --; } } // total為0，說明窗口中包含了p中所有字符 while(total == 0) { // (right - left + 1)代表窗口的大小 // 如果窗口的大小等於p，說明符合要求 if(right - left + 1 == p.length()){ // 記錄左指針 res.add(left); } // 左指針向右移動1個 char chl = s.charAt(left); left ++; // 如果左指針屬於p中 if(needs[chl - 'a'] > 0) { // 那麼窗口中該字符的數量也需要減1 window[chl - 'a'] --; // 如果窗口中該字符的數量小於需要的數量 if(window[chl - 'a'] < needs[chl - 'a']) { // 則total加1，跳出循環，說明還需要繼續向右尋找 total ++; } } } // 繼續向右尋找 right ++; } return res; }}/<integer>/<integer>/<code> 提交OK，執行時間加快了一個量級。
總結
以上就是這道題目我的解答過程了，不知道大家是否理解了。這道題主要是利用"窗口"這一概念，優化的時候可以利用題目本身的特殊性。
有興趣的話可以訪問我的博客或者關注我的公眾號、頭條號，說不定會有意外的驚喜。
https://death00.github.io/
閱讀更多 健程之道 的文章
