日野弥生：勉強しよう

sliding window

发表于2025年01月02日

介绍

滑动窗口（sliding window）是一种常见的算法技巧，通常用于解决字符串、数组等数据结构相关的问题。 滑动窗口算法的基本思想是维护一个滑动窗口，该窗口通常是一个固定大小的子序列，并且该子序列通常是连续的。然后，通过滑动窗口的方式，不断地更新窗口的位置和大小，以便解决问题。滑动窗口实质上就是队列。

介绍

在字符串S中使用双指针中的左右指针技巧，初始化left=right=0，把索引左闭右开区间 $[left, right)$ 称为一个窗口。

不断地增加 right 指针扩大窗口 $[left, right)$， 直到窗口中的字符串符合要求（包含了 T 中的所有字符）。此时停止增加right，转而不断增加left指针缩小窗口 $[left, right)$， 直到窗口中的字符串不再符合要求（不包含T中的所有字符了）。

同时，每次增加left，都要更新一轮结果。

重复第2和第3步，直到 right 到达字符串 S 的尽头。

例题

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

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

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

滑动窗口右边界滑动的条件是满足大于等于目标值，左边界是小于目标值，可以把所有满足条件的子数组在O(n)次遍历过程中寻找所有的子数组。找到其中长度最短的子数组。

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int slow=0,fast=0,sum=0,length=nums.size();
        bool fastMeet = false;
        for(;fast<nums.size();fast++)
        {
            sum+=nums[fast];
            while(sum>=target)
            {
                fastMeet=true;
                length=length<(fast-slow+1)?length:(fast-slow+1);
                sum-=nums[slow];
                slow++;
            }
        }
        return fastMeet?length:0;
    }
};