【算法小课堂】滑动窗口-Toy模板网

这篇具有很好参考价值的文章主要介绍了【算法小课堂】滑动窗口。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

滑动窗口

【算法小课堂】滑动窗口,算法小课堂,算法挨揍日记,算法

基本概念：

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

本质上就是同向双指针，窗口的范围就是[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;
    }
};