【算法攻坚】滑动窗口算法总结

滑动窗口

什么是滑动窗口？

滑动：指的是窗口是移动的，按照一定的方向来移动

窗口：指的是一定范围内，这个范围可以固定也可以是变化的

实例

常见的滑动窗口思想的实例有以下两个

• TCP协议中的滑动窗口协议，用于网络数据传输时的流量控制，以避免拥塞的发生
• 限流算法，滑动窗口限流，一定时间内允许对小窗口进行限流

算法题目

力扣中有很多滑动窗口的算大题目，大体分为如下几个

1. 无重复字符的最长子串
2. 串联所有单词的子串
3. 最小覆盖子串
4. 至多包含两个不同字符的最长子串
5. 长度最小的子数组
6. 滑动窗口最大值
7. 字符串的排列
8. 最小区间
9. 最小窗口子序列

共性

这些题目的共性是都具有单调性，随着左指针的增加，其最优的右指针单调不减

具有这种特性就能够使用滑动窗口算法一般模板解题

继续以昨天的题目为例【无重复字符的最长子串】：

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

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

3. 此时，我们停止增加 right，转而不断增加 left 指针缩小窗口 [left, right]，直到窗口中的字符串符合要求（不包含重复的字符串）。同时，每次增加 left前我们都要更新一轮结果，记录当前子串长度是否大于最长子串，如果大于则记录最长子串长度。

4. 重复第 2 和第 3 步，直到 right指针 到达字符

典型场景

1、数组或字符串、连续， 需要输出或比较的结果在原数据结构中是连续排列的（字符串中的连续不重复子串，数组中的连续元素最大和）

2、双指针，每次窗口滑动时，只需观察窗口两端元素的变化，窗口内元素的整体性比较强，窗口滑动可以只通过操作头尾两个位置的变化实现，但对比结果时往往要用到窗口中所有元素（检查窗口中是否含有重复字符，对比窗口中元素的和）

解题模板

说是模板其实也就是一些伪代码实现，具体问题再具体分析优化，灵活变通

变长滑动窗口

//构建窗口window容器保存窗口内元素，可以采用数组、hashset、hashmap等
window window;
//保存最优结果、最大或最小等
result = defaltvalue;
//构造窗口的左右边界指针
int left = 0, right = 0;
while(right < s.size()) {
    window.add(s[right]);
    //确定合适的位置，执行右指针移动，不一定就放在这
    right++;
    // 如果符合要求，说明窗口构造完成，移动 left 缩小窗口
    while (window 符合要求) {
        // 如果这个窗口的条件更优，则更新result
        result = maxOrMin(result, window);
        //移出左指针元素
        window.remove(s[left]);
        left++;
    }
}
return result;

固定长度滑动窗口：

// 固定窗口大小为 k
string s;
// 在 s 中寻找窗口大小为 k 时的所包含最大元音字母个数
int right = 0; 
while(right < s.size()) {
    window.add(s[right]);
    right++;
    // 如果符合要求，说明窗口构造完成，
    if (right>=k) {
        // 这是已经是一个窗口了，根据条件做一些事情
        // ... 可以计算窗口最大值等 
        // 最后不要忘记把 right -k 位置元素从窗口里面移除
    }
}
return result;    

小栗子

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

示例 1：

输入：target = 7, nums = [2,3,1,2,4,3] 输出：2 解释：子数组 [4,3] 是该条件下的长度最小的子数组。 示例 2：

输入：target = 4, nums = [1,4,4] 输出：1 示例 3：

输入：target = 11, nums = [1,1,1,1,1,1,1,1] 输出：0

1、首先分析是不是符合滑动窗口算法的定义

肯定是符合的了啊，数组、最小连续等关键字，很容易想到变长滑动窗口

2、利用模板方法解题

实现：

此题窗口不需要存原始元素只需要保留窗口内之和就可以

public int minSubArrayLen(int target, int[] nums) {
    //保留窗口内元素之和
    int sum = 0;
    //最短路径
    int minLength = Integer.MAX_VALUE;;
    int left =0, right =0;
    while(right < nums.length){
        sum += nums[right];
        //如果满足条件，则需要控制左指针移动
        while(sum >= target){
            minLength = Math.min(minLength, right-left + 1);
            sum-=nums[left];
            left++;
        }
        right ++ ;
    }
    return minLength == Integer.MAX_VALUE? 0: minLength;
}

小结

总结解题模板可以在做题时思路更明确，但也不能生搬硬套，要根据实际题目做出相应的优化取舍，才能比较高效的实现算法，还是需要多练、多思考。