滑动窗口

滑动窗口通常用于 子数组、子序列等关键词出现的题目中，其核心在于求 连续区间内满足某种条件的某个结果。

对于所有的滑动窗口题目，都可以将其总结成下面的四个步骤：

• 入：记录某个属性。

• 判断：判断是否满足属性，以方便再出操作时进行结果的更新。

• 更新：更新最终结果。

• 出：更新入操作记录的属性。

对于滑动窗口可以简单的分为两种类型：定长滑动窗口 和 不定长滑动窗口。

定长滑动窗口

​ 其中定长滑动窗口比较简单，下面举一个例子来讲解一下：

643. 子数组最大平均数 I - 力扣（LeetCode）

​ 分析：观察题目可知，需要再固定窗口大小的连续区间中求最大的平均数，因此入操作记录就是 长度为k的区间内数的和，判断操作用于判断计算的区间长度是否符合要求，更新操作用于更新最终返回结果，出操作用于更新记录的区间长度和的值。

class Solution {
public:
    double findMaxAverage(vector<int>& nums, int k) {
        double res = DBL_MIN , t = 0;
        int n = nums.size();
        bool flag = true;

        for (int i = 0; i < n; i++) 
        {
            t += nums[i]; // 入 
			
            // 判断
            int left = i - k + 1;
            if (left < 0)
                continue; 

            // 更新
            if (flag)
            {
                 res = t / k;
                 flag = false;
            }
            else 
                res = max(res, t / k);

            // 出
            t -= nums[left];
        }
        
        return res; 
    }
};

练习：1423. 可获得的最大点数 - 力扣（LeetCode）

不定长滑动窗口

​ 不定长滑动窗口可以大致分为：求最长子数组，求最短子数组，求子数组个数。对于求最长子数组和求最短子数组这两类题目其实差别不大，关键在于 判断条件。

​ 对于求子数组个数又可以范围：越短越好、越长越好、恰好某个长度三种。

求最长子数组

​ 例题：3. 无重复字符的最长子串 - 力扣（LeetCode）

​ 分析：观察题目可以得知，最关键在于子数组不能有重复字符，因此判断条件就是 cnt[s[i]] 需要 <= 1，所以在判断和出操作就需要何在一起，当满足条件后再进行更新。

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int res = 0;
        int n = s.size();
        int left = 0;
        unordered_map<char, int> cnt; // 要使用哈希表，不光只有字符

        for (int i = 0; i < n; i++) 
        {
            cnt[s[i] - 'a']++; // 入
            
            while (cnt[s[i] - 'a'] > 1) // 出、判断
            {
                cnt[s[left] - 'a']--;
                left++;
            }
            res = max(res, i - left + 1); // 更新
        }

        return res; 
    }
};

练习：

3090. 每个字符最多出现两次的最长子字符串 - 力扣（LeetCode）

1493. 删掉一个元素以后全为 1 的最长子数组 - 力扣（LeetCode）

求最短子数组

​ 其类型和求最长子数组相同，只是在判断条件地方需要进行调整。

​ 例题：209. 长度最小的子数组 - 力扣（LeetCode）

​ 分析：可以观察只有判断条件做出了调整，这是重点要关注的。当然针对这个题目，更新要放在出和判断操作的循环内部，因为如果t不会>= target时，将会返回res的最初值INT_MAX导致错误。

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int res = INT_MAX;
        int n = nums.size();
        int left = 0;
        int t = 0;
        
        for (int i = 0; i < n; i++) 
        {
            t += nums[i]; // 入

            while (t >= target) // 出
            {
                res = min(res, i - left + 1); // 更新 把更新放在这里可以考虑到所有情况
                t -= nums[left];
                ++left;
            }
        }

        return res == INT_MAX ? 0 : res;
    }
};

练习：

2904. 最短且字典序最小的美丽子字符串 - 力扣（LeetCode）

1234. 替换子串得到平衡字符串 - 力扣（LeetCode）

求子数组个数

越短越好

​ 对于越短越好的情况来说，一般要写成ans += i - left + 1。因为题目要求越短越好，当[left，i]满足条件时，[left + 1，i]、[left + 2，i]、[left + 3，i]……[i，i]都会满足，因此此时的子数字量为 i - left + 1。

​ 例题：713. 乘积小于 K 的子数组 - 力扣（LeetCode）

​ 分析：题目要求子数组的乘积严格小于k，这就是判断的关键条件，只需要在乘积大于等于k时进行 出操作即可，最后进行ans += i - left + 1。出了通用操作还需要进行k == 0特判 和 left <= i以防越界。

class Solution {
public:
    int numSubarrayProductLessThanK(vector<int>& nums, int k) {
        int n = nums.size();
        int left = 0;
        int mul = 1; 
        int ans = 0;

        for (int i = 0; i < n; i++) 
        {
            mul *= nums[i]; // 入

            while (left <= i && mul >= k)  // 出 判断
            {
                mul /= nums[left];
                left++;
            }
            ans += i - left + 1; // 更新
        }   

        return k == 0 ? 0 : ans; // 特判
    }
};

练习：

​ 3258. 统计满足 K 约束的子字符串数量 I - 力扣（LeetCode）

2302. 统计得分小于 K 的子数组数目 - 力扣（LeetCode）

越长越好

​ 对于越长越好的情况一般是要写 ans += left，因为要求越长越好，此时进行判断的条件时不满足条件的情况，所以当[left， i]不满足情况，[0， left - 1]的区间内所有子数组都满足条件，因此有left个子数组。

​ 例题：3325. 字符至少出现 K 次的子字符串 I - 力扣（LeetCode）

​ 分析：对于子数组越长越好，需要在判断时对题目条件反过来判断，然后在更新时ans += left即可。对于此题判断可以出的条件为 字符没有至少出现k次。然后在判断之后进行更新 ans += left。

class Solution {
public:
    int numberOfSubstrings(string s, int k) {
        int n = s.size();
        int ans = 0;
        int left = 0;
        int cnt[26] = {0};
        set<char> tmp;

        for (int i = 0; i < n; i++) 
        {
        	// 入
            cnt[s[i] - 'a']++;
            if (cnt[s[i] - 'a'] >= k) tmp.insert(s[i]);
            
            // 出 判断 
            while (tmp.size()) 
            {
                cnt[s[left] - 'a']--;
                if (cnt[s[left] - 'a'] < k)  tmp.erase(s[left]); // 这里为了不满足条件
                	left++;
            }
			
			// 更新
            ans += left;
        }

        return ans; 
    }
};

练习：

2962. 统计最大元素出现至少 K 次的子数组 - 力扣（LeetCode）

​ 1358. 包含所有三种字符的子字符串数目 - 力扣（LeetCode）

恰好某个长度

​ 对于恰好某个长度的情况：

​ 例如恰好元素和为k，多少个元素和 >= k的子数组 减去 多少个元素和 > k，也是 >= k + 1的子数组，这样可以同一操作，通过调用两次函数来获得结果。 至少问题，即就是上面地方**越长越好(ans += left)**的情况

​ 也可以看作 <= k 减去 <= k - 1，至多问题，转化成上面的**越短越好（ans += i - left + 1）**的情况。

​ 练习：930. 和相同的二元子数组 - 力扣（LeetCode）

​ 分析：可以将恰好和为goal子数组个数转转化为， >= toal（至少）子数组个数 减去 >= toal + 10（至少）子数组个数。

class Solution {
public:
    int slove(vector<int>& nums, int k) 
    {
        int n = nums.size();
        int ans = 0;
        int left = 0;
        int sum = 0;

        for (int i = 0; i < n; i++) 
        {
            sum += nums[i];
            while (left <= i && sum >= k) 
            {
                sum -= nums[left];
                left++;
            }
            ans += left; // 至多问题，越长越好，逆反条件
        }
        
        return ans; 
    }
    int numSubarraysWithSum(vector<int>& nums, int goal) {
        return slove(nums, goal) - slove(nums, goal + 1);
    }
};

练习：

​ 1248. 统计「优美子数组」 - 力扣（LeetCode）