基础算法(5)：滑动窗口

1.何为滑动窗口？

? ? ?滑动窗口其实也是一种算法，主要有两类：一类是固定窗口，一类是可变窗口。固定的窗口只需要一个变量记录，而可变窗口需要两个变量。

2.固定窗口

? ? ?就像上面这个图一样。两个相邻的长度为4的红色窗口，下一个窗口一定比前一个窗口少一个数据，以及多一个数据。

? ? ? 橙色为切换窗口时少的那个数据，黄色为多出来的那个数据，所以可以直接沿用之前数据，并且减去橙色数据，加上黄色数据，就是下一个窗口的值了。这就是滑动窗口的一个经典思路。

2.1 例题解析

? ? ? 首先题是这样的

给你一个整数数组arr和两个整数k和target。请你返回长度为k且平均值大于等于target的子数组数目。

? ? ? ?我们可以看到他已经确定了窗口的长度，像这种滑动窗口的问题，一般都是连续字串和连续子数组的问题，在我做过的题中还没有例外，这也是滑动窗口的应用限制，必须连续。下面让我们看看怎么写：

? ? ? ?(1)首先，统计前k个数的和sum，作为第一个窗口的值，并且判断是否满足sum>=target，如果满足，则计数器加一；

? ? ? ?(2)然后，窗口开始右移，以后每次通过前一个相邻窗口，计算得到下一个窗口的值，并且判断条件是否满足满足则计数器加一；

? ? ? ?(3)返回计数器的值；

nclude<iostream>
int numOfSubarrays(int* arr, int arrSize, int k, int target)
{
    int r;
    int sum = 0;
    int cnt = 0;
    for (r = 0; r < k; r++)
    {
        sum += arr[r];
    }
    if (sum >= target)cnt++;

    for (r = k; r < arrSize; r++)
    {
        sum -= arr[r - k];
        sum += arr[r];
        if (sum >= target)cnt++;
    }
    return cnt;
}

2.2 leetcode固定窗口题目及模板总结

2.2.1 定长字串中元音的最大数目??

class Solution {
public:
    int check(char c)//每次遇到一个字符都需要进行判断，所以我们自己实现一个函数，避免重复代码
    {
         if(c=='a'||c=='e'||c=='i'||c=='o'||c=='u')
         {
             return 1;
         }
         return 0;
    }
    int maxVowels(string s, int k) {
    int n=s.size();
    int r=0;//窗口边界
    int cnt=0;//计数器
    int sum=0;//比较迭代的变量
    for(;r<n;r++)//开始遍历
    {
       cnt+=check(s[r]);//向窗口内添加元素
       if(r>=k)//窗口长度大于给定值
        {
            cnt-=check(s[r-k]);滑动直到长度等于k，减去左边元素，向右不断滑动
        }
        sum=max(sum,cnt);//将sum和cnt的值进行比较，这里sum其实起到了比较作用，将cnt的值存储到sum中
    }
    return sum;
    }
};

2.2.2 长度最小的子数组

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int r;
        int result=INT32_MAX;
        int sum=0;
        int i=0;
        for(r=0;r<nums.size();r++)
        {
            sum+=nums[r];
            while(sum>=target){
                result=min(result,r-i+1);
                sum-=nums[i++];
            }
        }
        return result==INT32_MAX?0:result;
    }
};

? ? ? ?从这两道题中我们看到了一些相似的代码，这就是

2.2.3 固定窗口长度模板

int subarrays(int* arr, int k, int target)
{ 
    int n=arr.size();//数组长度
    int r;//窗口边界
    int cnt = 0;//一般用来求和或者计数，视题目而定
    int sum = 0;//比较迭代的变量
    for (; r < n; r++)//开始遍历
    {
        cnt += arr[r];//向窗口内添加元素
        if (r >= k)//窗口长度大于给定值
        {
            cnt -= arr[r - k]; //减去左边元素，向右不断滑动，直到长度等于k
        }
        sum = max(sum, cnt);//更新sum的值，将sum和cnt的值进行比较，这里sum其实起到了比较作用，将cnt的值存储到sum中
    }
    return sum;
}

3.非固定窗口

3.1 例题解析

给定一个二进制数组 nums 和一个整数 k，如果可以翻转最多 k 个 0 ，则返回 数组中连续 1 的最大个数 。

? ? ?这个题怎么写呢？这个可没有说求固定长度，你翻转最多k个0之后连续1的长度最大，这个长度就是数组中连续1的最大个数，那我们就把固定长度不固定就ok了啊，下面看代码解析：

int longestOnes(vector<int>& nums, int k) {
     int n=nums.size();//数组/字符串长度
     int sum=0;//用于统计子数组/子区间是否有效，看题目要求，可能是求和/计数
     int l=0;//双指针，代表遍历的区间
     int zerocnt=0;//统计0的个数
     for(int r=0;r<n;r++)
     {
         if(nums[r]==0)zerocnt++;//满足题目要求，计数器+1
         while(zerocnt>k)//翻转0的个数大于k
         {
            if(nums[l++]==0)zerocnt--;//那就开始滑动窗口了，左边界开始滑动，这时候需要判断左边界的数是不是0，是0则计数器-1，滑动到计数器的值等于k
         }
         sum=max(sum,r-l+1);//更新sum的值
     }
     return sum;
    }
};

? ? ?相信看完代码之后大家会发现，固定长度的滑动窗口，while循环的条件都是比较长度，而非固定长度的滑动窗口，虽然不是比较长度，但也有其他的条件进行限制，具体什么条件就需要看具体的题目了。

3.2 leetcode非固定窗口题目及模板总结

3.2.1 字符串的排列

class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        //滑动窗口
        unordered_map<char, int> win, need;
        //将子串的元素压入哈希表
        for (auto &i : s1){
            ++need[i];
        }
        //定义边界
        int right = 0, left = 0, n = s1.size(), num = s2.size(), count = 0;
        //进行滑动窗口
        for(;right < num;right++){
            //如果可以在哈希表中找到元素就压入到窗口中
            if (need.find(s2[right]) != need.end()){
                ++win[s2[right]];
                if (need[s2[right]] == win[s2[right]]){
                    ++count;
                }
            }
            while(right - left + 1 >= n){
                if (count == need.size()){
                    return true;
                }
                //缩小窗口
                if (need.find(s2[left]) != need.end()){
                    //缩小窗口的步骤其实跟扩大窗口的步骤是相反的
                    if (need[s2[left]] == win[s2[left]]){
                        --count;
                    }
                    --win[s2[left]];
                }
                left++;
            }
        }
        return false;
    }
};

3.2.2 最短超串

class Solution {
public:
    vector<int> shortestSeq(vector<int>& big, vector<int>& small) {
       int n=big.size();//数组长度
       unordered_map<int,int>win,need;//定义两个哈希表，一个存储子数组，一个存储窗口
       for(auto a:small)//将子数组压入哈希表中便于查找和比较
       {
           need[a]++;
       }
       int l=0,r=0;//定义双指针(变量)作边界
       vector<int>ans;//定义一个数组用来存储最短子数组的左端点和右端点
       int count=0;//计数器，用来计算长数组出现子数组元素的次数，便于条件处理
       int len=INT_MAX;//可以不断更新的长度len
       //开始滑动窗口
       for(;r<n;r++)
       {
           //扩大窗口
           if(need.find(big[r])!=need.end())
           {
             win[big[r]]++;
             if(need[big[r]]==win[big[r]])//防止重复
             {
                count++;  
             }
           }
           //开始缩小窗口
           while(count==need.size())
          {
             //进行获取最短超串
             if(len>r-l+1)//判断下一个窗口是否比上一个窗口长度小，如果小则更新len和ans数组的值
             {
                 ans={l,r};
                 len=r-l+1;
             }
              如果此时窗口左端的值在子数组的哈希表中耀进行特殊处理
             if(need.find(big[l])!=need.end())
             {
                
                 if(need[big[l]]==win[big[l]])
                 {
                     count--;
                 }
                 win[big[l]]--;
             }
             l++;
          }
       }
       return ans;
    }
};

3.3.3 非固定窗口模板

int slidingWindow(vector<int> nums) {
    int n = nums.size();
    int ans = 0;
    // 记录窗口内的元素及其个数，非必要
    map<int, int> um;
    // l：窗口左边界； r：窗口右边界
    int l = 0, r = 0;
    // r 指针负责探索新的区间，直到搜索到nums的某末尾
    for(;r < n;r++) {
        um[r]++;
        // 如果区间不满足条件，l指针右移，窗口收缩
        while (区间[l, r] is Invalid) {
            um[l]--;
            l++;
        }
        // 此处处理结果, deal with(ans, 区间[l, r])
        res = max(ans, r - l + 1); // 或者res = min(ans, r - l + 1);
    }
    return ans;
}