滑动窗口模板

209. 长度最小的子数组 – 力扣（LeetCode）

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

2302. 统计得分小于 K 的子数组数目 – 力扣（LeetCode）

class Solution {
public:
long long countSubarrays(vector<int>& nums, long long k) {
long long res = 0, cnt = 0;
int n = nums.size(), left = 0, right = 0;
while (right < n)
{
while (right < n && cnt < k)
{
if (right > left)
cnt /= right – left;
cnt += nums[right];
cnt *= right – left + 1;
right++;
}
if (cnt >= k)res += n – right + 1;
while (cnt >= k)
{
if (right > left)
cnt /= right – left;
cnt -= nums[left];
cnt *= right – left – 1;
left++;
if(cnt>=k)
res += n – right + 1;
}
}
return (long long)n*(n+1)/2-res;
}
};

 （1）设置滑动窗口左右窗口初始值均为0，然后右区间开始移动，直至找到满足条件的区间或来到数组末尾。

（2）如果当前区间符合条件，则添加到结果中。对于2302来说，当前区间满足，则后面的区间一定都满足，更新结果。

（3）移动左窗口，直至不满足条件。移动的过程中，只要移动一次仍然满足条件，则找到了一个满足条件的窗口，更新结果。