滑动窗口算法

发表于 更新于 分类于 Waline：

原理

滑动窗口算法的思路是这样：

1、我们在字符串 S 中使用双指针中的左右指针技巧，初始化 left = right = 0，把索引闭区间 [left, right] 称为一个「窗口」。

2、我们先不断地增加 right 指针扩大窗口 [left, right]，直到窗口中的字符串符合要求（包含了 T 中的所有字符）。

3、此时，我们停止增加 right，转而不断增加 left 指针缩小窗口 [left, right]，直到窗口中的字符串不再符合要求（不包含 T 中的所有字符了）。同时，每次增加 left，我们都要更新一轮结果。

4、重复第 2 和第 3 步，直到 right 到达字符串 S 的尽头。

这个思路其实也不难，**第 2 步相当于在寻找一个「可行解」，然后第 3 步在优化这个「可行解」，最终找到最优解。**左右指针轮流前进，窗口大小增增减减，窗口不断向右滑动。

示例

题目链接： https://leetcode-cn.com/problems/minimum-window-substring/

伪代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
string s, t;
// 在 s 中寻找 t 的「最小覆盖子串」
int left = 0, right = 0;
string res = s;

while(right < s.size()) {
    window.add(s[right]);
    right++;
    // 如果符合要求，移动 left 缩小窗口
    while (window 符合要求) {
        // 如果这个窗口的子串更短，则更新 res
        res = minLen(res, window);
        window.remove(s[left]);
        left++;
    }
}
return res;

具体实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/**
 * @param {string} s
 * @param {string} t
 * @return {string}
 */
var minWindow = function(s, t) {
    let start = 0, minLength = s.length + 10;
    let left = 0, right = 0;
    let needs = {}, where = {};
    t.split('').forEach((t1) => {
        needs[t1] = needs[t1] ? needs[t1] + 1 : 1;
    })
    let match = 0, needMatch = Object.keys(needs).length;
    while (right < s.length) {
        const s0 = s[right];
        if (!!needs[s0]) {
            where[s0] = where[s0] ? where[s0] + 1 : 1;
            if (where[s0] == needs[s0]) {
                match++;
            }
        }
        right++;
        while(match === needMatch) {
            if (right - left < minLength) {
                start = left;
                minLength = right - left;
            }
            const s1 = s[left];
            if (!!needs[s1]) {
                where[s1]--;
                if (where[s1] < needs[s1]) {
                    match--;
                }
            }
            left++;
        }
    }
    return minLength === s.length + 10 ? '' : s.substr(start, minLength);
};

不符合条件的最大值（2021/02/19更新）

上面的滑动窗口算法求取的是符合条件的最短长度。

但是有的时候我们求取的是不符合条件的最大长度。

举个例子，今天的leetcode每日一题

https://leetcode-cn.com/problems/max-consecutive-ones-iii/

题意转换。把「最多可以把 K 个 0 变成 1，求仅包含 1 的最长子数组的长度」转换为 「找出一个最长的子数组，该子数组内最多允许有 K 个 0 」

那么在这个题目中，条件就是：子数组中包含K个及以上个0。

这种情况下，我们的解题模板就变了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
string s, t;
// 在 s 中寻找 t 的「最小覆盖子串」
int left = 0, right = 0;
string res = s;

while(right < s.size()) {
    window.add(s[right]);
    right++;
    // 如果符合要求，移动 left 缩小窗口
    while (window 符合要求) {
        window.remove(s[left]);
        left++;
    }
    // 如果这个窗口的子串更长，则更新 res
    res = maxLen(res, window);
}
return res;

仔细观察可以发现，其实模板变化并不大，最重要的变化就是求结果的地方变了，从内层循环移动到了外层循环。

为什么会有这个变化呢？

要理解这个我们就要真正明白内外层的循环在做什么？

  • 外层循环在不断扩张子数组的长度，直到满足条件。换句话说，外层循环会遍历所有不符合条件的情况。

  • 内层循环在不断缩短子数组的长度，直到不满足条件。换句话说，就是内层循环会遍历所有符合条件的情况。

理解了这个，我们再来解决这个问题就不难了，直接上代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
var longestOnes = function(A, K) {
  let zeroCount = 0;
  let result = 0;
  let left = right = 0;
  while(right < A.length) {
    if (A[right] !== 1) {
      zeroCount++;
    }
    right++;
    while(zeroCount > K) {
      if (A[left] === 0) {
        zeroCount--;
      }
      left++;
    }
    result = Math.max(result, right - left);
  }
  return result;
};

看到这里可能会有人问，你只说了符合条件的最短和不符合条件的最长，那还有符合条件的最长和不符合条件的最短呢？

关于这个问题，大家可以思考一下，后面两个有没有意义，符合条件的最长，直接去判断整个数组是否符合条件就可以了，因为符合条件的最长只可能是整个数组，整个数组都不符合条件，子数组更不可能。而不符合条件的最短也是挨个遍历就行了，用数组中的每一项去判断是否符合条件就可以。

这两种情况根本用不到滑动窗口。