滑动窗口算法及其应用

概念

通过使用特定大小的子列表，在遍历完整列表的同时进行特定的操作，以达到降低了循环的嵌套深度。滑动窗口算法更多的是一种思想，而非某种数据结构的使用。

滑动窗口一般都是定义一个slow指针，然后一个fast指针不断向前滑动(循环遍历)，这个过程中我们要判断：

a. 是否找到了窗口；

b. 窗口是否满足要求；

c. 窗口缩减等；

使用场景

查找最大/最小k-子阵列，乘积，总和等

应用实战举例

1、连续元素最大和

给定数组，获取数组中n个连续元素，最大的和。例如：

// 输入：

// arr=[-3, 3, 1, -3, 2, 4, 7], n=3

// 输出：

// 13

// 连续三个数的最大和是 2 + 4 + 7 = 13

暴力解法，每次求出索引为 x 到 x + n 之间所有元素的和，再求出索引为 x+1 到 x+1 + n 的元素和，比较留下最大的那个，最后得到的结果就是最大的。

function maxSumSub0(arr, n) {

let len = arr.length;

if (n >= len) {

let sum = 0;

arr.forEach(item => sum += item);

return sum;

}

let maxSum = 0;

for (let i = 0; i + (n - 1) < len; i++) {

let tempSum = arr[i];

for (let j = 1; j < n; j++) {

tempSum += arr[i + j];

}

maxSum = Math.max(maxSum, tempSum);

}

return maxSum;

}

滑动窗口解法，先求出前 n 个元素的和 sum，之后每次都用 sum 减去第一个元素的值，再加上下一个元素的值，得到 sum1，留下 sum 和 sum1 中较大的那个即可。

function maxSumSub(arr, n) {

let len = arr.length;

let maxSum = 0;

if (n >= len) {

let sum = 0;

arr.forEach(item => sum += item);

return sum;

}

for (let i = 0; i < n; i++) {

maxSum += arr[i];

}

let windowSum = maxSum;

for (let i = n; i < len; i++) {

windowSum += (arr[i] - arr[i - n]);

maxSum = Math.max(maxSum, windowSum);

}

return maxSum;

}

2、无重复字符的最长子串

给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。

// 示例 1:

// 输入: "abcabcbb"

// 输出: 3

// 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

// 示例 2:

// 输入: "bbbbb"

// 输出: 1

// 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

// 示例 3:

// 输入: "pwwkew"

// 输出: 3

// 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。

// 请注意，你的答案必须是子串的长度，"pwke" 是一个子序列，不是子串。

解法一

用 Set 将字符存储在当前窗口[i,j)（最初j=i）中。然后我们向右侧滑动索引 j，如果它不在 Set 中，我们会继续滑动 j。直到 s[j] 已经存在于 Set 中。此时，我们找到的没有重复字符的最长子字符串将会以索引 i 开头。如果我们对所有的 i 这样做，就可以得到答案。

function lengthOfLongestSubstring(s) {

let n = s.length;

let set = new Set();

let ans = 0, i = 0, j = 0;

while (i < n && j < n) {

console.log('i = ' + i, 'j = ' + j, ans);

// try to extend the range [i, j]

if (!set.has(s.charAt(j))) {

set.add(s.charAt(j));

j++;

ans = Math.max(ans, j - i);

} else {

set.delete(s.charAt(i));

i++;

}

console.log([...set].join(''));

}

return ans;

}

lengthOfLongestSubstring('aaaabcdeefg');

解法二

上述的方法最多需要执行 2n 个步骤。事实上，它可以被进一步优化为仅需要 n 个步骤。我们可以定义字符到索引的映射，而不是使用集合来判断一个字符是否存在。当我们找到重复的字符时，我们可以立即跳过该窗口。

也就是说，如果在[i, j)范围内有与 j 重复的字符，我们不需要逐渐增加 i 。我们可以直接跳过 [i，j]范围内的所有元素，并将 i 变为 j + 1。

function lengthOfLongestSubstring1(s) {

let n = s.length;

let ans = 0;

let obj = {}; // current index of character

// try to extend the range [i, j]

for (let j = 0, i = 0; j < n; j++) {

if (obj[s.charAt(j)]) {

i = Math.max(obj[s.charAt(j)], i);

}

ans = Math.max(ans, j - i + 1);

obj[s.charAt(j)] = j + 1;

}

console.log(ans);

return ans;

}

lengthOfLongestSubstring1('aaaabcdeefg');

3、双滑动窗口

给定一个正整数数组 A，如果 A 的某个子数组中不同整数的个数恰好为 K，则称 A 的这个连续、不一定独立的子数组为好子数组。

（例如，[1,2,3,1,2] 中有 3 个不同的整数：1，2，以及 3。）

返回 A 中好子数组的数目。

// 示例 1：

// 输入：A = [1,2,1,2,3], K = 2

// 输出：7

// 解释：恰好由 2 个不同整数组成的子数组：[1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2].

// 示例 2：

// 输入：A = [1,2,1,3,4], K = 3

// 输出：3

// 解释：恰好由 3 个不同整数组成的子数组：[1,2,1,3], [2,1,3], [1,3,4].

分析：我们可以找两个窗口，window1和window2。其中，window1区间: (left1, right) 和 window2区间: (left2, right)，

只要满足如下两个条件：

1、window1区间恰好有K个不同整数

2、window2区间满足恰好有K-1个不同整数

这样就能保证：在[left1, left2]这个区间中，以left2为结尾的子数组都能满足恰好有K个不同整数。例如：

window1=[2,2,1,2,2], left1 = 0, right = 4,

window2=[2,2], left2 = 3, right = 4

以window[left2]结尾的并且符合要求的子数组：[2,2,1,2,2], [2,1,2,2], [1,2,2]，此时就是left2-left1=3。

class Window {

constructor() {

this.count = {};

this.diffNum = 0;

}

add(x) {

this.count[x] = (this.count[x] || 0) + 1;

if (this.count[x] === 1) {

this.diffNum++;

}

remove(x) {

this.count[x] = this.count[x] - 1;

if (this.count[x] == 0) {

this.diffNum--;

}

different() {

return this.diffNum;

}

function subarraysWithKDistinct(arr, K) {

const window1 = new Window();

const window2 = new Window();

let ans = 0, left1 = 0, left2 = 0;

for (let i = 0; i < arr.length; i++) {

let x = arr[i];

window1.add(x);

window2.add(x);

// 让window1左指针移动,直到等于K

while (window1.different() > K) {

window1.remove(arr[left1]);

left1++;

}

// 让window2左指针移动,直到恰好小于K

while (window2.different() >= K) {

window2.remove(arr[left2]);

left2++;

}

// window2恰好少一个，window1恰好有K个

// 这时所有以left2为结尾的子数组，都是符合要求的

ans += left2 - left1;

}

return ans;

}

本文到此结束。其实，不只是滑动窗口算法，其他的算法也是一样，都是一种思想，在真正解题的时候，最主要的还得看题目要求是啥，找到最合适的解法才是最重要的。

贵兴博客

滑动窗口算法及其应用

概念

使用场景

应用实战举例

相关文章

发表评论

发表评论