【算法】滑动窗口

基本思想

滑动窗口，也叫尺取法，就是不断的调节子序列的起始位置和终止位置，从而得出我们要想的结果，可以用来解决一些查找满足一定条件的连续区间的性质（长度等）的问题。

在暴力解法中，是一个for循环滑动窗口的起始位置，一个for循环为滑动窗口的终止位置，用两个for循环 完成了一个不断搜索区间的过程。这样的操作在面对极大的数据量是，效率极低。

而滑动窗口法是维护两个指针来进行操作，通常情况下时间复杂度为O(N)。

应用场景

1. 一般给出的数据结构是数组或者字符串
2. 求取某个子串或者子序列最长最短等最值问题或者求某个子序列的和等于目标值时

应用实例

以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;
}

水果成篮

这个题目的大致意思就是要使得窗口里面只有两种数并且长度最长，可以使用滑动窗口来解决。

1. 可以考虑用哈希表（数组模拟）保存窗口中数字出现的次数；
2. end指针每次向右移动，如果是没有出现的数字，则cnt++；
3. 如果cnt>2,则说明窗口中出现了三个数，此时需要收缩窗口；
4. 直到窗口中的数字出现次数减到0（hash[fruits[start]]--，start++），cnt--;
5. 然后重复上述流程。

代码如下：

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;
}

总结

滑动窗口法可以用来解决一些查找满足一定条件的连续区间的性质（长度等）问题，实际上就是双指针法，两个指针都从原点开始，一前一后，遇到不同的条件，移动不同的指针，左指针收缩窗口，右指针扩大窗口，最终得到问题的答案。