【进阶算法】滑动窗口

一、滑窗思想

滑动窗口，简称滑窗，是快慢指针的一种应用技巧，两个指针之间形成一个窗口，右指针不断扩张，左指针按条件收缩，随着窗口的扩大和缩小找到满足条件的答案。

滑窗分为 2 种：

• 静态窗口：窗口中的元素个数不变；
• 动态窗口：窗口中的元素个数随条件变化。

二、适用场景

滑动窗口适用于：查找满足一定条件的最长或最短子数组、子字符串。

三、滑窗使用思路

3.1 查找最长

-- 左右双指针（L, R）在起始点，R 向右逐位滑动

---- 每次滑动过程中

       如果窗口内元素满足条件，R 增加，扩大窗口，并更新最优结果

       如果窗口内元素不满足条件，L 增加，缩小窗口

-- R 到达结尾

3.2 查找最短

-- 左右双指针（L, R）在起始点，R 向右逐位滑动

---- 每次滑动过程中

       如果窗口内元素不满足条件，R 增加，扩大窗口

       如果窗口内元素满足条件，L 增加，缩小窗口，并更新最优结果

-- R 到达结尾

3.3 两个重要问题

1. 什么时候扩大窗口，什么时候收缩窗口？

2. 在扩大窗口还是收缩窗口时更新结果？

  -- 获取最长的时候，满足条件扩大窗口、更新结果，不满足条件收缩窗口；

       -- 获取最短的时候，满足条件收缩窗口、更新结果，不满足条件扩大窗口。

四、代码框架

int left = 0, right = 0;

while (right < size()) {
    // 移入窗口的元素
    window.add(s[right]);
    // 窗口增大
    right++;
    
    // 如果窗口需要收缩
    while (left < right && window needs shrink) {
        // 移出窗口的元素
        window.remove(s[left]);
        // 缩小窗口
        left++;
    }
}

五、练习题目

LeetCode 209. 长度最小的子数组

LeetCode 76. 最小覆盖子串 

LeetCode 3. 无重复字符的最长子串