LeetCode-滑動窗口-找到字符串中所有字母異位詞

?? 關于專欄：專欄用于記錄 prepare for the coding test。

---

📝 找到字符串中所有字母異位詞

🎯題目描述

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

🔗題目鏈接：找到字符串中所有字母異位詞

🔍 輸入輸出示例

示例 1:

輸入: s = "cbaebabacd", p = "abc"
輸出: [0,6]
解釋:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的異位詞。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的異位詞。

示例 2:

輸入: s = "abab", p = "ab"
輸出: [0,1,2]
解釋:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的異位詞。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的異位詞。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的異位詞。

🧩題目提示

• 1 <= s.length, p.length <= 3 * 104
• s 和 p 僅包含小寫字母

🧪滑動窗口—定長

本題適合使用 定長滑動窗口，即窗口長度固定為 p.size()，從左往右滑動，每次滑動判斷當前窗口是否是異位詞。

我們用兩個長度為 26 的數組來統計字母頻次（因為僅包含小寫字母），當兩個數組相等時（array支持$==$?直接比較），說明當前窗口是 p 的異位詞。

1.預處理字符串 p 的字符頻率，用一個長度為 26 的數組 cnt_p 存儲。

2.滑動窗口遍歷 s，維護當前窗口內的頻率數組 cnt_s。

3.若 cnt_s 與 cnt_p 相等，則窗口起始位置是一個異位詞。

class Solution {
public:vector<int> findAnagrams(string s, string p) {vector<int> ans;array<int,26> cnt_s {};array<int,26> cnt_p {};for(char c : p){cnt_p[c - 'a']++;}for(int right = 0;right < s.size();right++){cnt_s[s[right] - 'a']++;int left = right - p.size() + 1;if(left >= 0){if(cnt_s == cnt_p){ans.push_back(left);}cnt_s[s[left]-'a']--;}else{continue;}}return ans;}
};

🧪滑動窗口—變長

相比固定窗口的方法，我們也可以用靈活窗口（變長）去嘗試：

• 每次將右指針加入窗口，并對字符頻率計數；
• 若某個字符頻率多了，就不斷移動左指針直到頻率合法；
• 當窗口長度等于 p.size()，說明找到一個異位詞。

class Solution {
public:vector<int> findAnagrams(string s, string p) {vector<int> ans;array<int,26> cnt {};for(char c : p){cnt[c - 'a']++;}int left = 0;for(int right = 0;right < s.size();right++){int c = s[right] - 'a';cnt[c]--;while(cnt[c] < 0){cnt[s[left] - 'a']++;left++;}if(right - left + 1 == p.size()){ans.push_back(left);}}return ans;}
};

🌟 總結

• 使用字符頻率數組作為滑動窗口核心；

• 左指針控制窗口合法性，右指針推動遍歷；

• 比較頻率數組是否一致，作為是否匹配的判斷依據。

滑動窗口維度	技巧要點
指針控制	一般使用 left 和 right 兩個指針定義區間 [left, right] 或 [left, right)
窗口內數據維護	統計頻率、子串長度、計數器（如滿足條件的字符個數）等
何時收縮窗口	取決于當前窗口是否滿足題意或已經不合法
何時記錄結果	當窗口滿足題意時保存起始索引或其他信息

知識點	簡要描述
滑動窗口	一種通過左右指針控制子串區域的技巧，適合處理子串/子數組問題
字符頻率匹配	通過數組或哈希表統計字符出現次數，判斷是否為異位詞
固定長度滑窗	每次窗口長度固定，對新字符加入、舊字符移出，保持頻率平衡
數組比較	std::array<int, 26> 支持 == 運算，效率高于 unordered_map

🔁 相似題目推薦（逐步進階）

難度	題目	題目編號	技巧
🌱 簡單	字符串的排列	567	判斷是否包含某異位詞
🌿 中等	本題	438	找出所有異位詞起始位置
🌳 中等	最小覆蓋子串	76	滑窗 + 字符要求計數器
🌲 困難	串聯所有單詞的子串	30	復雜頻率統計、窗口倍增