长度最小的子数组（滑动窗口）
题目描述
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其总和大于等于 target 的长度最小的子数组[numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
示例
示例 1：
输入：target = 7, nums = [2,3,1,2,4,3] 输出：2 解释：子数组[4,3]是该条件下的长度最小的子数组。
示例 2：
输入：target = 4, nums = [1,4,4] 输出：1
示例 3：
输入：target = 11, nums = [1,1,1,1,1,1,1,1] 输出：0
题解
先给出滑动窗口的模板代码
for(扩展右边界){
while(condition){
更新区间
缩小左边界
}
}其中，扩展右区间的过程就是遍历数组的过程
滑动窗口的思想：
- 定义两个指针 start 和 end 分别表示子数组（滑动窗口窗口）的开始位置和结束位置
- 维护满足题意的区间条件并更新区间
文字不好描述，我们直接看这道题
- 首先我们使用两个指针固定一个区间，并计算这个区间的数值和
- 判断区间和是否大于等于target，如果不满足这个题意条件，就扩展右区间
- 假如我们找到了一个满足题意的区间[left,right]，此时就记录并更新区间长度
- 此时就不能再继续扩展右边界了，因为题目要求的是找最小的区间长度，再继续扩展显然区间长度会变大，因此就尝试缩小左边界
- 缩小左边界时会遇到两种情况
- 缩小后的区间[left0,right]（其中left0表示缩小后的边界值），仍旧满足题意，则更新区间长度，同时继续尝试缩小左侧边界
- 缩小后的区间[left0,right]（其中left0表示缩小后的边界值），不满足题意，则不能再缩小左侧边界，此时的区间已经不满足题意，那么再缩小显然也不满足题意，于是继续扩展右边界
手动模拟过程如下所示
代码模拟如下
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
//定义左边界
int i=0;
//定义结果变量
int res=INT_MAX;
//用于计算子区间的和
int sum=0;
//不断扩展右边界，相当于在遍历数组
for(int j=0;j<nums.size();++j){
//右边界在遍历数组的过程中计算区间和
sum+=nums[j];
//当满足题意时，就记录并更新子区间的长度，同时缩小左边界
while(sum>=target){
res=min(res,j-i+1);
//更新区间和，并缩小左边界
sum-=nums[i++];
}
}
return (res==INT_MAX)?0:res;
}
};其中
sum-=nums[i++];这段代码相当于
sunm-=nums[i];
i++;因为缩短左边界的同时还要保存区间长度和sum
原文地址：https://blog.csdn.net/qq_58158950/article/details/143605014
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！