目录
滑动窗口,也叫尺取法,就是不断的调节子序列的起始位置和终止位置,从而得出我们要想的结果,可以用来解决一些查找满足一定条件的连续区间的性质(长度等)的问题。
在暴力解法中,是一个for循环滑动窗口的起始位置,一个for循环为滑动窗口的终止位置,用两个for循环 完成了一个不断搜索区间的过程。这样的操作在面对极大的数据量是,效率极低。
而滑动窗口法是维护两个指针来进行操作,通常情况下时间复杂度为O(N)。
以Leetcode上的一个题目为例子:
这个题目的暴力解法当然就是两个for循环,然后不断的寻找符合条件的子序列,时间复杂度很明显是O(n^2),这样的解法在Leetcode上也会超时。
那么我们可以试着用滑动窗口的方法来看看。
滑动窗口的方法通过一个for循环来达到目的,那问题又来了,for循环表示的是窗口的起始位置,还是终止位置?
我们可以先假设for循环表示的窗口的起始位置,那么我们又该如何遍历数组?如果再设置一个循环,那这个方法就和暴力解法无异了。
所有,for循环表示的是滑动窗口的终止位置,我们也可以通过这个题目来验证一下。
以题目中的数组nums=[2,3,1,2,4,3],目标和target=7为例,来模拟一下滑动窗口的运行过程:
根据子序列和的大小不断调整滑动窗口的大小,当和小于target时,end++;当和大于等于target时,start++,在移动过程中,当sum==target时,记录并不断更新L的值,使得最后得到满足其和 ≥ target 的长度最小的连续子数组
代码如下:
int minSubArrayLen(int target, int* nums, int numsSize) {
int start=0;
int end=0;
int sum=0;
int suml=0;
int result=numsSize+1;
for(end;end<numsSize;end++)
{
sum+=nums[end];
while(sum>=target)
{
suml=end-start+1;
result=fmin(result,suml);
sum-=nums[start];
start++;
}
}
return result==numsSize+1?0:result;
}
这个题目的大致意思就是要使得窗口里面只有两种数并且长度最长,可以使用滑动窗口来解决。
代码如下:
int totalFruit(int* fruits, int fruitsSize) {
int hash[100001]={0};
int start=0;
int end=0;
int max=0;
int cnt=0;
for(end;end<fruitsSize;end++)
{
if(hash[fruits[end]]==0)
{
cnt++;
}
hash[fruits[end]]++;
if(cnt<=2)
{
max=fmax(max,end-start+1);
}
while(cnt>2&&start<fruitsSize)
{
hash[fruits[start]]--;
if(hash[fruits[start]]==0)
{
cnt--;
}
start++;
}
}
return max;
}
滑动窗口法可以用来解决一些查找满足一定条件的连续区间的性质(长度等)问题,实际上就是双指针法,两个指针都从原点开始,一前一后,遇到不同的条件,移动不同的指针,最终得到问题的答案。