Sliding Window Algorithm - tenji/ks GitHub Wiki

滑动窗口

一、概念

学过计算机网络的同学，都知道滑动窗口协议（Sliding Window Protocol），该协议是 TCP协议 的一种应用，用于网络数据传输时的流量控制，以避免拥塞的发生。该协议允许发送方在停止并等待确认前发送多个数据分组。由于发送方不必每发一个分组就停下来等待确认。因此该协议可以加速数据的传输，提高网络吞吐量。

滑动窗口是一种解决问题的思路和方法，通常用来解决一些连续问题。滑动窗口算法是在给定特定窗口大小的数组或字符串上执行要求的操作。该技术可以将一部分问题中的嵌套循环转变为一个单循环，因此它可以减少时间复杂度。

二、与双指针的区别

双指针：

  • 计算过程仅与两端点相关的称为双指针；
  • 不固定大小；
  • 双指针是解决问题的一种方法；
  • 双指针可以同向移动可以双向移动；
  • 同向移动的双指针和滑动窗口没有任何联系。

滑动窗口：

  • 计算过程与两端点表示的区间相关的称为滑动窗口；
  • 默认固定大小的窗口，在一些条件触发的情况下，可能会将其大小进行修改。
  • 滑动窗口本身并不是解决问题的一种方法（或者说算法），它其实就是问题本身。
  • 滑动窗口一定是同向移动的。
  • 滑动窗口是一类问题，不同的问题需要使用不同的算法和数据结构来解决。

三、常见套路

滑动窗口主要用来处理连续问题。比如题目求解“连续子串 xxxx”，“连续子数组 xxxx”，就应该可以想到滑动窗口。能不能解决另说，但是这种敏感性还是要有的。

从类型上说主要有：

  • 固定窗口大小；
  • 窗口大小不固定，求解最大的满足条件的窗口；
  • 窗口大小不固定，求解最小的满足条件的窗口；

后面两种我们统称为可变窗口。当然不管是哪种类型基本的思路都是一样的，不一样的仅仅是代码细节。

3.1 固定窗口大小

对于固定窗口，我们只需要固定初始化左右指针 l 和 r，分别表示的窗口的左右顶点，并且保证：

  1. l 初始化为 0
  2. 初始化 r，使得 r - l + 1 等于窗口大小
  3. 同时移动 l 和 r
  4. 判断窗口内的连续元素是否满足题目限定的条件
    • 4.1 如果满足，再判断是否需要更新最优解，如果需要则更新最优解
    • 4.2 如果不满足，则继续。

3.2 可变窗口大小

对于可变窗口，我们同样固定初始化左右指针 l 和 r，分别表示的窗口的左右顶点。后面有所不同，我们需要保证：

  1. l 和 r 都初始化为 0
  2. r 指针移动一步
  3. 判断窗口内的连续元素是否满足题目限定的条件
    • 4.1 如果满足，再判断是否需要更新最优解，如果需要则更新最优解。并尝试通过移动 l 指针缩小窗口大小。循环执行 4.1
    • 4.2 如果不满足，则继续。

形象地来看的话，就是 r 指针不停向右移动，l 指针仅仅在窗口满足条件之后才会移动，起到窗口收缩的效果。

四、伪代码模板

int left = 0, right = 0; // 初始化双指针

// window 用于计数器，具体类型根据窗口内需要记录的内容而定，比如 HashSet、HashMap 等

while (right < s.size()) {
    window.add(s[right]);
    right++; // 移动右窗口
    
    while (valid) {
        window.remove(s[left]);
        left++; // 移动左窗口
    }
}

其中 window 的数据类型可以视具体情况而定，比如上述题目都使用哈希表充当计数器，当然你也可以用一个数组实现同样效果，因为我们只处理英文字母。

稍微麻烦的地方就是这个 valid 条件，为了实现这个条件的实时更新，我们可能会写很多代码。比如前两道题，看起来解法篇幅那么长，实际上思想还是很简单，只是大多数代码都在处理这个问题而已。

五、分析样例

5.1 题目描述（无重复字符的最长子串）

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

示例 1:

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

示例 4:

输入: s = ""
输出: 0

提示：

  • 0 <= s.length <= 5 * 104
  • s 由英文字母、数字、符号和空格组成

5.2 题目分析

遇到子串问题，首先想到的就是滑动窗口技巧。

类似之前的思路，使用 window 作为计数器记录窗口中的字符出现次数，然后先向右移动 right，当 window 中出现重复字符时，开始移动 left 缩小窗口，如此往复。

5.3 代码实现

public int lengthOfLongestSubstring(String s) {
    /*
    思路：最长子串，典型的连续子串问题，使用滑动窗口算法解决
     */

    int left = 0, right = 0;
    Map<Character, Integer> window = new HashMap<>(); // 窗口计数器

    int res = 0; // 记录最长长度
    while (right < s.length()) {
        char rightChar = s.charAt(right);
        if (window.get(rightChar) == null) {
            window.put(rightChar, 1);
        } else {
            window.put(rightChar, window.get(rightChar) + 1);
        }
        right++; // 移动右窗口

        while (window.get(rightChar) > 1) {
            // 如果窗口内有重复
            char leftStr = s.charAt(left);
            window.put(leftStr, window.get(leftStr) - 1);
            left++; // 移动左窗口
        }

        res = Math.max(res, right - left);
    }

    return res;
}

需要注意的是，因为我们要求的是最长子串，所以需要在每次移动 right 增大窗口时更新 res，而不是像之前的题目在移动 left 缩小窗口时更新 res。

六、Leecode 题目

参考链接