Problem: 438. 找到字符串中所有字母異位詞
題目：給定兩個字符串 s 和 p，找到 s 中所有 p 的 異位詞 的子串，返回這些子串的起始索引。不考慮答案輸出的順序。

【LeetCode 熱題 100】438. 找到字符串中所有字母異位詞——（解法一）定長滑動窗口+哈希表
【LeetCode 熱題 100】438. 找到字符串中所有字母異位詞——（解法二）定長滑動窗口+數組

整體思路

這段代碼同樣用于在字符串 s 中查找所有模式串 p 的異位詞。它采用了一種更為巧妙和高效的 可變大小滑動窗口 算法。與前兩個版本（一個用 HashMap，一個用固定大小窗口的數組）相比，此版本的核心思想是維護一個“合法”的窗口，該窗口內的字符都是 p 所需要的。

算法的整體思路可以分解為以下步驟：

1. 初始化“需求”計數器：

   • 算法使用一個大小為 26 的整型數組 cnt。這個數組的含義非常關鍵：它首先被初始化為模式串 p 的字符頻率，代表著我們“需要”的字符及其數量。
   • 例如，如果 p = "aab"，則 cnt['a'-'a'] 為 2，cnt['b'-'a'] 為 1。

2. 滑動窗口的擴張與收縮：

   • 算法使用 left 和 right 兩個指針來定義滑動窗口 [left, right]。right 指針持續向右移動，以擴大窗口。
   • 擴張與“消耗”：當 right 指針掃過 s 中的一個字符 c 時，會執行 cnt[c]--。這可以理解為“消耗”掉了一個所需的字符 c。
     • 如果消耗后 cnt[c] 仍 >= 0，說明這個字符是 p 所需要的，且目前窗口內該字符的數量尚未超出 p 的需求。
     • 如果消耗后 cnt[c] < 0，這說明窗口內已經包含了多余的字符 c（即超出了 p 的需求量）。
   • 收縮以維持“合法性”：
     • 一旦 cnt[c] 變為負數，就觸發 while 循環。這個循環的目的是收縮窗口的左邊界 left，直到窗口再次變得“合法”。
     • 收縮時，將 left 指針指向的字符“歸還”給計數器（cnt[s.charAt(left) - 'a']++），然后將 left 右移。
     • 這個過程會一直持續，直到我們剛剛加入的那個多余字符 c 的計數 cnt[c] 不再為負。

3. 判定與記錄結果：

   • 在每一次 right 指針移動后（并可能伴隨著 left 的移動），算法會檢查當前窗口 [left, right] 的大小。
   • 如果窗口大小 right - left + 1 正好等于模式串 p 的長度 m，這意味著：
     1. 窗口內沒有多余的字符（因為 while 循環保證了所有 cnt 值都 >= 0）。
     2. 窗口的總字符數正好是 m。
   • 這兩個條件同時滿足的唯一情況就是：窗口內的字符頻率與 p 完全匹配。因此，這是一個異位詞，將其起始索引 left 加入結果列表。

這種方法的精髓在于，它不強制窗口大小始終為 m，而是靈活地收縮窗口以排出“無效”字符，一旦窗口在“有效”狀態下長度恰好為 m，就找到了一個解。

完整代碼

import java.util.ArrayList;
import java.util.List;class Solution {/*** 在字符串 s 中查找 p 的所有異位詞的起始索引。* 此版本使用可變大小的滑動窗口和單個計數數組，非常高效。* @param s 主字符串 (假定只包含小寫字母)* @param p 模式字符串 (假定只包含小寫字母)* @return 一個包含所有匹配起始索引的列表*/public List<Integer> findAnagrams(String s, String p) {// ans 用于存儲結果，即所有異位詞的起始索引List<Integer> ans = new ArrayList<>();int n = s.length();int m = p.length();// 如果主串比模式串還短，直接返回空列表if (n < m) {return ans;}// cnt 數組作為字符頻率計數器。// 初始時，它存儲了模式串 p 中需要的各個字符的數量。int[] cnt = new int[26];for (char ch : p.toCharArray()) {cnt[ch - 'a']++;}// left 是滑動窗口的左邊界int left = 0;// right 是滑動窗口的右邊界，它將遍歷整個主串 sfor (int right = 0; right < n; right++) {// 獲取右邊界字符并將其映射到索引int c = s.charAt(right) - 'a';// 將該字符的所需數量減 1，表示窗口“消耗”了該字符。cnt[c]--;// 關鍵邏輯：處理窗口內字符冗余的情況。// 如果 cnt[c] < 0，說明窗口內字符 c 的數量已經超出了 p 的需求。// 此時需要從左側收縮窗口，直到 cnt[c] 恢復到 0。while (cnt[c] < 0) {// "歸還" 左邊界字符：將其在 cnt 數組中的計數加 1。cnt[s.charAt(left) - 'a']++;// 移動左邊界，縮小窗口。left++;}// 檢查窗口大小是否等于模式串的長度。// 因為 while 循環保證了窗口內沒有多余字符（所有 cnt[i] >= 0），// 如果此時窗口大小恰好為 m，那么它必然是一個異位詞。if (right - left + 1 == m) {ans.add(left);}}// 返回最終的結果列表return ans;}
}

時空復雜度

時間復雜度：O(N + M)

1. 模式串頻率統計：for (char ch : p.toCharArray()) 循環遍歷模式串 p 一次，時間復雜度為 O(M)，其中 M 是 p 的長度。
2. 滑動窗口遍歷：
   • 外層的 for 循環由 right 指針驅動，從 0 到 n-1，所以 right 指針總共移動了 N 次。
   • 內層的 while 循環由 left 指針驅動。雖然它在 for 循環內部，但 left 指針也只是一直向右移動，永不后退。
   • 在整個算法的生命周期中，left 指針最多從 0 移動到 n。
   • 每個字符 s.charAt(i) 最多被 right 指針訪問一次，也最多被 left 指針訪問一次。因此，兩個指針的總移動次數是線性的，約為 2N。
   • 所有數組操作 cnt[...]-- 和 cnt[...]++ 都是 O(1) 的。

綜合分析：
總的時間復雜度是預處理 p 的時間加上兩個指針遍歷 s 的時間，即 O(M) + O(N) = O(N + M)。這是一個非常高效的線性時間復雜度。

空間復雜度：O(k) 或 O(1)

1. 主要存儲開銷：算法只使用了一個額外的整型數組 cnt。
   • 該數組的大小是 26，這是一個固定的常數，代表了字符集的大小（k=26）。它不隨輸入 s 或 p 的長度而改變。
2. 結果列表：ans 列表用于存儲輸出，其空間不計入算法的輔助空間復雜度。
3. 其他變量：n, m, left, right, c 等都占用常數空間 O(1)。

綜合分析：
算法所需的額外輔助空間主要由 cnt 數組決定。由于其大小是固定的，空間復雜度為 O(k)，其中 k=26。因為 k 是一個常數，所以通常也稱其空間復雜度為 O(1)。