LCR 015. 找到字符串中所有字母異位詞

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

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

法1：滑動窗口

分析：

看例子s = "abab", p = "ab"

如果p的長度 大于 s的長度，說明s中不存在字母異位詞，則返回空列表

定義pCount,將p中每個字母的出現次數存一下，pCount[0]表示字母a在p中出現次數；

先對比索引0處，是不是字母異位詞。

遍歷s前面和p一樣長度的字符，將這部分s中字母頻數記錄到windowCount,此時，如果pCount和windowCount各個元素值相同，則下標0是字母異位詞，就將0加到結果中。

接著再遍歷s在p.length后的字符串，

索引每忘右移一下，就將當前元素的頻數加到windowCount中，也需減去當前索引-p.length下標元素頻數去掉，這樣保持每次計算的頻數長度與p的長度想用，每次都比較pCount和windowCount各個元素值相同，相同則將i - p.length + 1加入結果。

時間復雜度：$O(n)$

空間復雜度：$O(n)$

var findAnagrams = function(s, p) {if (s.length < p.length) return [];let result = [];let pCount = new Array(26).fill(0); // 用來記錄 p 中每個字符的頻率let windowCount = new Array(26).fill(0); // 用來記錄當前窗口中每個字符的頻率// 將 p 中每個字符的頻率記錄到 pCount 數組中for (let i = 0; i < p.length; i++) {pCount[p.charCodeAt(i) - 'a'.charCodeAt(0)]++;}// 初始化滑動窗口的第一個窗口for (let i = 0; i < p.length; i++) {windowCount[s.charCodeAt(i) - 'a'.charCodeAt(0)]++;}// 如果第一個窗口是變位詞，加入結果if (arraysAreEqual(pCount, windowCount)) {result.push(0);}// 滑動窗口遍歷字符串 sfor (let i = p.length; i < s.length; i++) {// 新加入的字符windowCount[s.charCodeAt(i) - 'a'.charCodeAt(0)]++;// 移除左邊的字符windowCount[s.charCodeAt(i - p.length) - 'a'.charCodeAt(0)]--;// 檢查當前窗口是否為變位詞if (arraysAreEqual(pCount, windowCount)) {result.push(i - p.length + 1);}}return result;
};// 輔助函數：檢查兩個頻率數組是否相等
function arraysAreEqual(arr1, arr2) {for (let i = 0; i < 26; i++) {if (arr1[i] !== arr2[i]) {return false;}}return true;
}