題目描述:給定字串 s 和 p,找出 s 中所有 p 的異位詞(anagram)的起始索引。異位詞即字母相同但排列不同的字串。
解題思路:滑動視窗是標準解法。維護長度為 p.size() 的固定視窗,用兩個頻率陣列分別記錄 p 和當前視窗的字元計數。視窗右移時加入右端字元、移除左端字元,更新計數陣列。若兩個陣列相等,則當前視窗起點為有效異位詞位置。陣列比較可在 O(26) = O(1) 時間內完成。
時間複雜度:O(n) — 滑動視窗遍歷 s 一次,每次視窗移動 O(26) = O(1) 比對。
空間複雜度:O(1) — 兩個固定大小 26 的計數陣列。
1. Initialize pCount[26] and wCount[26] for first window of size m 2. If pCount == wCount, add index 0 to result 3. Slide window from i = m to n-1: a. Add s[i] to window: wCount[s[i]-'a']++ b. Remove s[i-m] from window: wCount[s[i-m]-'a']-- c. If pCount == wCount, add (i - m + 1) to result 4. Return result
差值計數器 O(n):維護單一差值陣列和「匹配字元數」計數器 matches;加入/移除字元時更新 matches,當 matches == 26 時記錄起始位置 — 避免每次 memcmp,常數因子更小。
排序比對 O(n × m log m):對每個長度 m 的子字串排序後與 p 的排序版本比對 — 正確但過慢,在大輸入時會 TLE。
p 可以包含重複字元,現有解法是否仍然正確?