跳到主要内容

滑动窗口学习

参考资料 滑动窗口算法基本原理与实践（大部分内容转载自这里）

注意：滑动窗口也是一种双指针算法；

记录一下这个滑动窗口的原理，主要就是 LeetCode 的第三题，如下所示

无重复字符的最长子串​

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

示例 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 由英文字母、数字、符号和空格组成

什么是滑动窗口？​

滑动窗口算法在一个特定大小的字符串或数组上进行操作，而不在整个字符串和数组上操作，这样就降低了问题的复杂度，从而也达到降低了循环的嵌套深度。其实这里就可以看出来滑动窗口主要应用在数组和字符串上。

如下例子所示，设定滑动窗口（window）大小为 3，当滑动窗口每次划过数组时，计算当前滑动窗口中元素的和，得到结果 res。

可以 用来解决一些查找满足一定条件的连续区间的性质（长度等）的问题。由于区间连续，因此当区间发生变化时，可以通过旧有的计算结果对搜索空间进行剪枝，这样便减少了重复计算，降低了时间复杂度。

往往类似于 “ 请找到满足 xx 的最 x 的区间（子串、子数组）的 xx ” 这类问题都可以使用该方法进行解决。

需要注意的是，滑动窗口算法更多的是一种思想，而非某种数据结构的使用。

滑动窗口法的大体框架​

在介绍滑动窗口的框架时候，先从字面理解下：

  • 滑动：说明这个窗口是移动的，也就是移动是按照一定方向来的。
  • 窗口：窗口大小并不是固定的，可以不断扩容直到满足一定的条件；也可以不断缩小，直到找到一个满足条件的最小窗口；当然也可以是固定大小。

为了便于理解，这里采用的是字符串来讲解。但是对于数组其实也是一样的。滑动窗口算法的思路是这样：

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

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

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

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

下面画图理解一下，needs 和 window 相当于计数器，分别记录 T 中字符出现次数和窗口中的相应字符的出现次数。

初始状态：

增加 right，直到窗口 [left, right] 包含了 T 中所有字符：

现在开始增加 left，缩小窗口 [left, right]。

直到窗口中的字符串不再符合要求，left 不再继续移动。

之后重复上述过程，先移动 right，再移动 left…… 直到 right 指针到达字符串 S 的末端，算法结束。

上述过程对于非固定大小的滑动窗口，可以简单地写出如下伪码框架：

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;

解题方法​

看完了滑动窗口，这里就可以写出上面那题的解题方法了

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s.length() < 1) {
            return 0;
        }

        int right = 0;
        int left = 0;
        int length = 0;
        Set set = new HashSet();

        while (right < s.length()) {
            if (set.contains(s.charAt(right))) {
                // 当出现重复的应该从头开始删，直到删到重复那个位置为止
                set.remove(s.charAt(left++)); // 删完，left 指针移动一位
            } else {
                set.add(s.charAt(right++));
            }
            // 每次循环都更新一次 length 长度
            length = set.size() > length ? set.size() : length; 
        }

        return length;
    }
}