【算法小课堂】滑动窗口

深藏阁楼爱情的钟 2024-03-01 08:06 77阅读 0赞

## 滑动窗口 ##

![在这里插入图片描述][68694b06872046779b9583c7ea02acc2.png_pic_center]

### 基本概念： ###

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

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

![image-20230925150305094][]

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

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

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

### 核心思想： ###

三步走：

*  窗口的形成初期![image-20230925151043949][]
 *  进窗口

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

![image-20230925151412135][]

窗口范围如图所示

*  判断

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

*  出窗口

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

![image-20230925151736685][]

*  更新结果

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

### 具体示例： ###

> **可见算法挨揍日记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;
        }
    };

### 适用题目类型总结： ###

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

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

![在这里插入图片描述][0ea450b26f564cebaf6389d3a6d6d83b.gif_pic_center]

、

[68694b06872046779b9583c7ea02acc2.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/01/f066deecdf47456aa8454c2dd39b6e53.png
[image-20230925150305094]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/01/b2daf786a8b0475b8bcea0b1339c85cb.png
[image-20230925151043949]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/01/9b8fa64768a3485b98039ad15bcc7b19.png
[image-20230925151412135]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/01/41af7fa856ce416ebb24681bccd5aae3.png
[image-20230925151736685]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/01/2e2a5ccd88bb4b9594f0099703f5cc3a.png
[0ea450b26f564cebaf6389d3a6d6d83b.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/01/e5112de771ac45fd87badad8f002bf20.png