- 站点信息
- 问题反馈
- 邮箱：[email protected]
- 吐槽一下
关注微信
©2020-2025 ioDraw All rights reserved,
Privacy Policy
此题用到的方法是滑动窗口（唬人叫法）
但其实滑动窗口并不难，本质上还是双指针，只不过换了一个马甲而已，我们定义一个fast指针，一个slow指针，不断的计算从slow指针到fast指针之间的值
我们以力扣给出的示例作解释
我们令fast指针 =0；令slow指针=0
再定义一个计算 从slow指针到fast指针的总和的 int变量sum
以及用来统计符合要求的连续子数组长度的count变量
此时sum的值=2，小于target值 ，我们就移动fast指针来扩大sum的值。
此时sum的值=5，小于target的值，继续移动fast指针来扩大sum的值，依次类推，我们发现当fast指向第四个元素
2 的时候，下标值等于7，记录此时的数组长度count
此时我们再次移动fast指针
此时我们发现sum的值已经大于7了，那么这个时候我们就移动slow指针向前
此时sum的值仍然大于7，我们就继续移动slow指针
我们发现此次sum的值又符合条件，就判断此时的数组长度是否小于之前的count，如果小于就更新count的值。
依次类推，终止条件为slow指针指向最后一个数组元素的时候。我们就能够遍历完整个数组，找出所有满足我们sum等于target的连续子数组。
这个题的思路为利用动态窗口统计出所有符合要求的连续子数组，获取他的长度(我们这里的方法是fast指针-slow指针+1
)，然后不断与之前的count值进行比较，如果小于就更新，最终遍历结束之后返回count就可以了
以下为该题的实现
int minSubArrayLen(int target, int* nums, int numsSize){
//暴力写法会超时，因此我们学习滑动窗口写法，本质上还是双指针。
int fast=0;
int slow=0;
int min=1000000;//用来存储更新之后的最小长度
int sum=0;
while(fast<numsSize)
{
sum=sum+nums[fast];
while(sum>=target)
{
int count=fast-slow+1;//计算当前长度
if(min>count)
{
min=count;
}
sum-=nums[left++];
}
fast++;
}
if(min==1000000)//如果没有满足条件的子字符串
{
return 0;
}
return min;
}
总结：
1.动态窗口可以实现快速的处理连续的数据。
2.动态窗口有两种：
1.长度变换的动态窗口，也就是我们这种。
2.长度不变换的动态窗口。
3.什么情况可以用滑动窗口来解决实际问题呢？
* 一般给出的数据结构是数组或者字符串
* 求取某个子串或者子序列最长最短等最值问题或者求某个目标值时
* 该问题本身可以通过暴力求解
结束！