滑动窗口
解题思路
初始化两个 hash 数组，用于记录 s 和 p 中的字符；
滑动窗口的大小等于 p 的长度，每次向右滑动的时候判断两个 hash 数组是否内容相等，相等则说明存在 异位词 ，将滑动窗口的左边界索引放入结果数组中；
窗口滑动的过程中，要维护窗口内的元素个数；
复杂度
-
时间复杂度：
O(N) -
空间复杂度：
O(1)
代码实现
function findAnagrams(s, p) {
const result = [];
if (s.length < p.length) return result;
// 1. 初始化两个 hash 数组
const sCount = new Array(26).fill(0);
const pCount = new Array(26).fill(0);
const offset = 'a'.charCodeAt(0); // 定义偏移量
// 2. 初始化频率数组，保证了窗口的大小与 p 的长度一致
for (let i = 0; i < p.length; i++) {
pCount[p.charCodeAt(i) - offset]++;
sCount[s.charCodeAt(i) - offset]++;
}
// 3. 滑动窗口
for (let i = p.length; i <= s.length; i++) {
// 窗口比较
if (arraysAreEqual(pCount, sCount)) {
result.push(i - p.length);
}
// 向右滑动窗口
sCount[s.charCodeAt(i - p.length) - offset]--;
sCount[s.charCodeAt(i) - offset]++;
}
return result;
}
// 辅助函数，用于比较两个数组是否相等
function arraysAreEqual(arr1, arr2) {
for (let i = 0; i < 26; i++) {
if (arr1[i] !== arr2[i]) return false;
}
return true;
}
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 541. 反转字符串 II
上一篇
评论
