【算法小课堂】滑动窗口

滑动窗口

基本概念：

滑动窗口本质是双指针算法的一种演变

本质上就是同向双指针，窗口的范围就是[left,right）

滑动窗口大致可以分为两类

• 窗口大小不变的
• 窗口大小变化的

滑动窗口遇到一些验证重复性的问题的时候可以用哈希表来优化

核心思想：

三步走：

• 窗口的形成初期
  
• 进窗口
  

开始遍历数组，right一直向右走直到遇到题目的判断条件，假设到了如下位置：

窗口范围如图所示

• 判断

这个时候进行判断，具体得看题目，而判断结束后先出窗口还是先更新结果得看具体题目

• 出窗口

判断结束后，right不再移动，而left向前移动，窗口大小也随之改变

• 更新结果

根据具体题目的要求，写出更新结果的条件和语句

具体示例：

可见算法挨揍日记05-08

https://leetcode.cn/problems/minimum-size-subarray-sum/

本题就是在出窗口之前

时间复杂度：虽然代码是两层循环，但是我们的 left 指针和 right 指针都是不回退的，两者

最多都往后移动 n 次。因此时间复杂度是 O(N) 。

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int length = INT_MAX;
        int n = nums.size();
        int left = 0;
        int right = 0;
        int sum = 0;
        while(right<n)
        {
            sum+=nums[right];
            while(sum>=target)
            {
                length=min(length,right-left+1);
                sum-=nums[left++];
            }
            right++;
        }
        return length==INT_MAX?0:length;
    }
};

适用题目类型总结：

分析的对象是「⼀段连续的区间」，因此可以考虑「滑动窗⼝」的思想来解决

常见于子区间的最长最短问题等等

、