問題描述

給定兩個字符串 s 和 p，要求找到 s 中所有是 p 的**字母異位詞（Anagram）**的子串的起始索引。
字母異位詞是指由相同字母重新排列形成的字符串（包含相同的字母且每個字母出現的次數相同）。
例如：

• 輸入：s = "cbaebabacd", p = "abc"
  輸出：[0, 6]
  解釋：s 中從索引 0 開始的 "cba" 和索引 6 開始的 "bac" 均為 "abc" 的異位詞。

---

核心思路：滑動窗口 + 字符計數數組

1. 字符計數數組

• 核心思想：通過固定長度的數組（長度26，對應26個小寫字母）記錄字符串中每個字符的出現次數。
• 比較機制：若兩個字符串的字符計數數組相同，則它們是字母異位詞。

2. 滑動窗口

• 窗口初始化：在 s 中初始化一個長度為 p.length() 的窗口。
• 窗口滑動：每次向右移動窗口，移除左邊界字符的計數，增加右邊界字符的計數。
• 實時比較：每次滑動后檢查當前窗口的計數數組是否與 p 的計數數組一致。

---

算法步驟

1. 邊界處理：若 s 的長度小于 p 或 p 為空，直接返回空列表。
2. 初始化計數數組：
   • pCount：統計 p 中每個字符的出現次數。
   • sCount：統計 s 中初始窗口（前 p.length() 個字符）的出現次數。
3. 初始窗口檢查：若初始窗口的計數與 p 一致，記錄索引 0。
4. 滑動窗口遍歷：
   • 窗口每次右移一位，更新左邊界字符的計數（減少）和右邊界字符的計數（增加）。
   • 每次更新后檢查計數數組是否匹配，若匹配則記錄當前窗口的起始索引。

---

完整代碼實現

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;public class Solution {public List<Integer> findAnagrams(String s, String p) {List<Integer> result = new ArrayList<>();int m = p.length();int n = s.length();// 邊界條件處理if (m == 0 || n < m) {return result;}int[] pCount = new int[26]; // 記錄p的字符計數int[] sCount = new int[26]; // 記錄當前窗口的字符計數// 初始化p和s的初始窗口的字符計數for (int i = 0; i < m; i++) {pCount[p.charAt(i) - 'a']++;sCount[s.charAt(i) - 'a']++;}// 檢查初始窗口是否匹配if (Arrays.equals(pCount, sCount)) {result.add(0);}// 滑動窗口：每次移動一位，更新sCount并檢查for (int i = 1; i <= n - m; i++) {// 移除左邊界字符的計數int leftChar = s.charAt(i - 1);sCount[leftChar - 'a']--;// 添加右邊界字符的計數int rightChar = s.charAt(i + m - 1);sCount[rightChar - 'a']++;// 檢查當前窗口是否匹配if (Arrays.equals(pCount, sCount)) {result.add(i);}}return result;}
}

---

復雜度分析

• 時間復雜度：O(n)，其中 n 是字符串 s 的長度。
  滑動窗口遍歷 s 需要 O(n)，每次窗口操作（更新計數和比較）的時間為常數。
• 空間復雜度：O(1)，使用固定長度的兩個長度為26的數組。

---

關鍵點總結

1. 字符計數數組：利用數組索引映射字符，快速統計字符出現次數。
2. 滑動窗口優化：避免每次重新計算整個子串的計數，通過動態更新窗口邊界字符的計數保證高效性。
3. 邊界處理：注意字符串長度不足時的直接返回邏輯。

---

類似問題

• LeetCode 567. 字符串的排列：判斷 s2 是否包含 s1 的排列。
• LeetCode 76. 最小覆蓋子串：尋找覆蓋目標字符的最短子串。