Problem: 438. 找到字符串中所有字母異位詞
題目：給定兩個字符串 s 和 p，找到 s 中所有 p 的 異位詞 的子串，返回這些子串的起始索引。不考慮答案輸出的順序。
【LeetCode 熱題 100】438. 找到字符串中所有字母異位詞——（解法一）定長滑動窗口+哈希表
【LeetCode 熱題 100】438. 找到字符串中所有字母異位詞——（解法三）不定長滑動窗口+數組
整體思路
這段代碼同樣旨在解決 “在一個字符串 s 中找出所有模式串 p 的異位詞” 的問題。與上一個使用 HashMap 的版本相比，此版本采用了 固定大小的數組 作為頻率計數的工具，這是一種針對特定字符集（此處為小寫英文字母）的常見優化。
算法的核心思路依然是 滑動窗口，但具體實現細節有所不同：
-
數據結構選擇與預處理：
- 該實現選擇了兩個大小為 26 的整型數組
cntP和cntS來分別存儲模式串p和當前滑動窗口的字符頻率。 - 前提與優勢：這個選擇基于一個重要假設——輸入字符串
s和p只包含小寫英文字母。利用char - 'a'的技巧，可以將每個字符映射到數組的0-25索引上，這比HashMap更快且內存占用更低。 - 首先，代碼遍歷模式串
p，將其字符頻率統計到cntP數組中。這個數組是固定不變的“目標”。
- 該實現選擇了兩個大小為 26 的整型數組
-
一體化的滑動窗口遍歷：
- 與上一個版本先初始化窗口再滑動的兩步法不同，此版本將窗口的初始化、擴張、校驗和收縮整合在一個
for循環中。 - 循環由一個
right指針驅動，從頭到尾遍歷主串s。 - 窗口擴張：在每次迭代中，首先將
right指針指向的字符計入窗口頻率數組cntS。 - 窗口形成與校驗：通過
left = right - m + 1計算出窗口的左邊界。if (left < 0)這個條件用于處理窗口還未形成完整大小（長度為m）的初始階段。在窗口大小不足m時，只進行擴張，不進行比較和收縮。- 當
left >= 0時，說明窗口已經達到了m的長度。此時，使用Arrays.equals(cntP, cntS)來比較兩個頻率數組。Arrays.equals會逐一比較數組中的每個元素，如果所有元素都相等，則證明當前窗口內的子串是p的一個異位詞，將其起始索引left加入結果列表。
- 窗口收縮：在完成校驗后（無論是否匹配），將
left指針指向的字符從窗口中移除（即在cntS中將其頻率減一），為下一次迭代做準備。這樣，窗口就整體向右平移了一格。
- 與上一個版本先初始化窗口再滑動的兩步法不同，此版本將窗口的初始化、擴張、校驗和收縮整合在一個
-
返回結果：
- 循環結束后，返回包含所有起始索引的結果列表
ans。
- 循環結束后，返回包含所有起始索引的結果列表
這種一體化的實現方式代碼更緊湊，邏輯流程非常清晰：每一步都“加一個右邊的，（可能的話）比一下，再減一個左邊的”。
完整代碼
class Solution {/*** 在字符串 s 中查找 p 的所有異位詞的起始索引。* 此版本使用數組進行頻率統計，優化了性能。* @param s 主字符串 (假定只包含小寫字母)* @param p 模式字符串 (假定只包含小寫字母)* @return 一個包含所有匹配起始索引的列表*/public List<Integer> findAnagrams(String s, String p) {// ans 用于存儲結果，即所有異位詞的起始索引List<Integer> ans = new ArrayList<>();// n 是主串 s 的長度，m 是模式串 p 的長度int n = s.length();int m = p.length();// 如果主串比模式串還短，直接返回空列表if (n < m) {return ans;}// cntS: 存儲當前滑動窗口內子串的字符頻率// cntP: 存儲模式串 p 的字符頻率// 使用大小為 26 的數組，因為題目隱含了輸入為小寫英文字母int[] cntS = new int[26];int[] cntP = new int[26];// 步驟 1: 統計模式串 p 中每個字符的出現次數for (char c : p.toCharArray()) {// 'c' - 'a' 將字符映射到 0-25 的索引cntP[c - 'a']++;}// 步驟 2: 滑動窗口遍歷主串 sfor (int right = 0; right < n; right++) {// a. 窗口擴張：將右邊界字符加入窗口的頻率統計中cntS[s.charAt(right) - 'a']++;// 計算當前窗口的左邊界索引int left = right - m + 1;// 判斷窗口是否已形成。當 left < 0 時，窗口大小不足 m，跳過比較和收縮步驟。if (left < 0) {continue;}// b. 窗口內校驗：當窗口大小正好為 m 時，比較窗口和模式串的頻率數組// Arrays.equals() 逐元素比較兩個數組，如果完全相同則返回 trueif (Arrays.equals(cntP, cntS)) {// 如果是異位詞，將當前窗口的起始索引 left 加入結果列表ans.add(left);}// c. 窗口收縮：將即將移出窗口的左邊界字符的頻率減一cntS[s.charAt(left) - 'a']--;}// 返回最終的結果列表return ans;}
}
時空復雜度
時間復雜度：O(N + M)
- 模式串頻率統計：
for (char c : p.toCharArray())循環遍歷模式串p一次。設p的長度為M，此步驟時間復雜度為 O(M)。 - 滑動窗口遍歷：
for (int right = 0; right < n; right++)循環遍歷主串s一次。設s的長度為N，此循環執行N次。- 在循環內部：
- 數組的讀寫操作（
cntS[...]++和cntS[...]--）是 O(1) 的。 Arrays.equals(cntP, cntS)操作需要比較兩個數組中的所有元素。由于數組大小是固定的 26，所以比較的次數也是常數 26。因此，該操作的時間復雜度為 O(26)，即 O(1)。
- 數組的讀寫操作（
- 所以，整個循環的時間復雜度是
N次 O(1) 操作，總計為 O(N)。
- 在循環內部：
綜合分析：
總時間復雜度 = 預處理 p 的時間 + 遍歷 s 的時間 = O(M) + O(N) = O(N + M)。
由于通常 N 是遠大于 M 的，所以有時也近似地稱為 O(N)，但 O(N + M) 是更精確的表述。
空間復雜度：O(k) 或 O(1)
- 主要存儲開銷：算法使用了兩個整型數組
cntS和cntP。- 每個數組的大小都是 26，這是一個固定的常數，不隨輸入字符串
s和p的長度變化而變化。 k在這里代表字符集的大小，即 26。
- 每個數組的大小都是 26，這是一個固定的常數，不隨輸入字符串
- 其他變量：
n,m,right,left等變量占用的是常數空間 O(1)。 - 結果列表：
ans列表用于存儲輸出，其空間不計入輔助空間復雜度。
綜合分析：
算法所需的額外輔助空間主要由兩個頻率數組決定。由于數組大小是固定的，所以空間復雜度是 O(k)，其中 k=26。因為 k 是一個常數，所以也可以表述為 O(1)。這表示算法占用的額外內存是一個常數，非常高效。
