滑动窗口是双指针法的一种高级用法。 双指针法。滑动窗口就是不断调节子数组的起始位置和终止位置,得到我们想要的结果。解题的关键在于如何移动起始位置。
如下图所示,设定滑动窗口(window)大小为 3,当滑动窗口每次划过数组时,计算当前滑动窗口中元素的和,得到结果 res
一、适用条件
适用条件为:
- 数组
- 字符串
- 求解的结果具有某种特质的子数组或者子字符串。
二、方法总结
实现滑动窗口需要确定以下三点:
- 窗口内的元素
保持窗口内数值总和大于或等于numsSize的长度最小的连续子数组。
for(int j=0;j<numsSize;j++){ sum+=nums[j]; while(sum>=numsize){ xxx; sum-=nums[i++];//滑动窗口的精髓,不断调节子数组的初始位置 } }
- 如何移动窗口的起始位置
当前窗口值的值大于numsize,则窗口向前移动,也就是i指针向前移动,缩小
while(sum>=numsize){ subLength=j-i+1;//获取子数组长度 result=result<subLength?result:subLength; sum-=nums[i++];//滑动窗口的精髓,不断调节子数组的初始位置 }
- 如何移动窗口的终点位置
通过for循环遍历指针即可
for(int j=0;j<numsSize;j++){ }
三、窗口滑动具体案例
根据例题:
- step1:滑动窗口的起始位置
- step2:移动窗口的结束位置,记录窗口值
- step3:移动窗口的起始位置当前窗口值的值大于numsize,则窗口向前移动,也就是i指针向前移动,缩小
int minSubArrayLen(int target, int* nums, int numsSize){ int result=INT32_MAX;//更新值 int i=0;//step1:滑动窗口的起始位置 int sum=0;//滑动窗口的数值之和 int subLength;//子数组的长度 for(int j=0;j<numsSize;j++){//step2:移动窗口的结束位置,记录窗口值 sum+=nums[j]; //step3:移动窗口的起始位置当前窗口值的值大于numsize,则窗口向前移动,也就是i指针向前移动,缩小 while(sum>numsSize){ subLength=j-i+1; result=result<subLength?result:subLength; sum-=nums[i++];//滑动窗口的精髓,不断调节子数组的初始位置 } } return result==INT32_MAX?0:result;//查看有没有被赋值 }