原文題目
Given two strings s and p, return an array of all the start indices of p's anagrams in s. You may return the answer in any order.

題目摘要

1. 給定兩個字符串 s 和 p，回傳包含 p 的所有字母異位詞在 s 中的起始索引的陣列。
2. 回傳的答案順序可以是任意的。

Example 1:

Input: s = "cbaebabacd", p = "abc"
Output: [0,6]
Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".

Example 2:

Input: s = "abab", p = "ab"
Output: [0,1,2]
Explanation:
The substring with start index = 0 is "ab", which is an anagram of "ab".
The substring with start index = 1 is "ba", which is an anagram of "ab".
The substring with start index = 2 is "ab", which is an anagram of "ab".

解題思路

1. 初步檢查：
   • 如果字串 s 的長度小於 p，則不可能存在異位詞，直接返回空結果。
2. 設置陣列來記錄字母出現次數：
   • 使用兩個長度為 26 的陣列 pCount 和 sCount 分別來儲存字串 p 和 s 中的字母出現次數。這裡假設字母都是小寫字母，因此每個字母可以對應到數組的索引位置，'a' 對應索引 0，'b' 對應索引 1，以此類推。
3. 初始化窗口：
   • 首先，計算 p 中每個字母的出現次數，並同時計算 s 中與 p 等長的第一個窗口的字母出現次數。
4. 滑動窗口：
   • 使用滑動窗口技術在 s 中從左向右移動，窗口的大小始終保持與 p 相同。每次移動後，更新窗口內字母的出現次數：
     1. 比較當前窗口內的字母頻次是否與 p 相同。
     2. 如果相同，則將當前窗口的起始索引加入結果列表。
     3. 然後，將滑動窗口的右邊界新增一個字母，左邊界移除一個字母。
5. 處理最後一個窗口：
   • 當滑動窗口遍歷到最後一個位置後，需要再次比較當前窗口的字母出現次數是否匹配。如果匹配，則將起始索引加入結果。
6. 回傳結果：
   • 最後，回傳所有找到的異位詞的起始索引列表。

class Solution { 
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> result = new ArrayList<>(); //設立一個結果列表，用來存放找到的字母異位詞的起始索引
        
        //如果 s 的長度小於 p 的長度，不可能存在異位詞，直接返回空結果
        if (s.length() < p.length()) {
            return result;
        }

        int[] pCount = new int[26]; //用來儲存 p 中每個字母的出現次數
        int[] sCount = new int[26]; //用來儲存 s 的當前窗口中每個字母的出現次數

        //初始化 pCount 和 sCount，針對 p 和 s 中第一個與 p 長度相同的窗口
        for (int i = 0; i < p.length(); i++) {
            pCount[p.charAt(i) - 'a']++;
            sCount[s.charAt(i) - 'a']++;
        }

        //滑動窗口遍歷 s，開始從第 0 個位置滑動
        for (int i = 0; i < s.length() - p.length(); i++) {
            //如果當前窗口中的字母頻次與 p 相匹配，則該窗口為異位詞，將索引 i 加入結果列表
            if (matches(pCount, sCount)) {
                result.add(i);
            }
            
            sCount[s.charAt(i + p.length()) - 'a']++; //將滑動窗口右邊界的新字母加入統計
            sCount[s.charAt(i) - 'a']--; //移除滑動窗口左邊界的字母
        }

        //處理最後一個窗口
        if (matches(pCount, sCount)) {
            result.add(s.length() - p.length());
        }

        return result; //回傳最終找到的所有異位詞起始索引
    }

    //比較兩個頻次數組是否完全相同
    private boolean matches(int[] pCount, int[] sCount) {
        for (int i = 0; i < 26; i++) {
            if (pCount[i] != sCount[i]) {
                return false;
            }
        }
        return true; //當所有字符頻次匹配時，回傳 true
    }
}

結論
這題運用了滑動窗口來解決在一個大字串 s 中尋找所有異位詞的問題。通過預先計算字母的出現次數，並利用固定大小的窗口滑動來保持對子字串字母的統計，我們能夠在每次滑動中快速比對目標字串 p 和當前窗口的字母分佈。這個方法的有效降低了時間複雜度，因為每次窗口的移動只需要常數時間來更新字母的出現次數，這比重新計算每個子字串的出現次數效率更高。透過這題練習，讓我更加理解滑動窗口的應用。