前文总结过子数组相关问题可以简单的分为三类，使用的方法可分为三种，即：「前缀和」「滑动窗口」「动态规划」。详情可见 秒杀子数组类题目
而今天这一篇是「滑动窗口解决子数组问题」的专题！！(主要是遇到了一种用滑动窗口的高级小技巧，忍不住想分享出来)
先来回顾一下「滑动窗口解决子数组问题」的两个特点：
>=target的子数组 或者 乘积严格小于k那么废话不多说，直接今天的题目！！！
题目详情可见 水果成篮
首先我们分析一下题目是否符合「滑动窗口解决子数组问题」中总结的两个特点
「只有两个篮子，并且每个篮子只能装单一类型的水果，要求摘到的水果数量最多」说人话就是「子数组中最多只能包含两个不同的元素，求子数组的最大长度」
是不是「研究对象」为单个的元素，而不是子数组的元素之和！！
是不是「约束条件」为一个范围，即：不同元素的数量>= k
说白了，这就是一个典型的「滑动窗口解决子数组问题」的模版题，控制滑动窗口移动的因素是窗口内不同元素的个数
下面给出完整代码：
xxxxxxxxxxpublic int totalFruit(int[] fruits) { Map<Integer, Integer> window = new HashMap<>(); int left = 0, right = 0; int ans = 0; while (right < fruits.length) { int c = fruits[right++]; window.put(c, window.getOrDefault(c, 0) + 1); // 窗口内不同元素的数量 > k，开始收缩窗口 while (window.size() > 2) { int d = fruits[left++]; window.put(d, window.get(d) - 1); // 从窗口内删除该元素 if (window.get(d) == 0) window.remove(d); } // 允许到此处时，说明「窗口内不同元素的数量 <= k」，满足要求，更新答案 // 每次都是以 right 结尾的子数组大小 ans = Math.max(ans, right - left); } return ans;}题目详情可见 区间子数组个数
按照惯例，首先我们分析一下题目是否符合「滑动窗口解决子数组问题」中总结的两个特点
「最大元素在范围[left, right]中的所有子数组个数」
是不是「研究对象」为单个的元素，而不是子数组的元素之和！！
是不是「约束条件」为一个范围，即：left <= max <= right
如果我们想把窗口内最大元素控制在left <= max <= right范围中，其实是不可行的，会出现答案的不完整，有兴趣的可以去模拟一下整个过程
这个时候我们需要曲线救国：如果我们把最大元素<= right的子数组数量算出来，然后再把最大元素<= left - 1的子数组数量算出来，两者相减不就是最终答案了嘛
其实我们可以把「约束条件」中的第二个特点再限定一波：必须是[-∞, k]或者[k, +∞]。如果遇到[left, right]这种范围可以转换一下，来一波曲线救国
下面给出完整代码：(这个题目相对而言比较简单，所以可能没有很明显的滑动窗口模版的那些套路，但底层的原理就是滑动窗口)
xxxxxxxxxxpublic int numSubarrayBoundedMax(int[] nums, int left, int right) { // [left, right] = [-∞, right] - [-∞, left - 1] return notGreater(nums, right) - notGreater(nums, left - 1);}// 计算最大元素不大于 r 的子数组数量private int notGreater(int[] nums, int target) { int cnt = 0, ans = 0; for (int num : nums) { // 以 num 结尾的子数组满足要求 if (num <= target) cnt += 1; // 否则 cnt 重新开始计数 else cnt = 0; // 更新结果 ans += cnt; } return ans;}题目详情可见 K 个不同整数的子数组
上个题目「滑动窗口」不是很明显，这个题目就超级明显，可以说是滑动窗口的亲儿子了
按照惯例，首先我们分析一下题目是否符合「滑动窗口解决子数组问题」中总结的两个特点
「不同整数的个数恰好为k的所有子数组个数」
是不是「研究对象」为单个的元素，而不是子数组的元素之和！！
但是这个「约束条件」确给出了给出了具体的限定，即：不同整数的个数恰好为k
下面给出一种错误版本的代码：
xxxxxxxxxxpublic int subarraysWithKDistinct(int[] nums, int k) { Map<Integer, Integer> window = new HashMap<>(); int left = 0, right = 0; int ans = 0; while (right < nums.length) { int g = nums[right++]; window.put(g, window.getOrDefault(g, 0) + 1); // 收缩窗口 while (window.size() > k) { int d = nums[left++]; window.put(d, window.get(d) - 1); if (window.get(d) == 0) window.remove(d); } // 更新答案 // 以 nums[right] 结尾的子数组数量 if (window.size() == k) { ans += (right - left); } } return ans;}对于样例[1,2,1,2,3]，会遗漏答案[2,1]
其实可以很明显的看出来，对于一个具体区间的限定，如本题可以看作[k, k]，而上一题是[left, right]，在收缩窗口的时候会出现一些问题，所以我们需要像上一题一样曲线救国
如果我们把不同整数的个数<= k - 1的子数组数量算出来，然后再把不同整数的个数<= k的子数组数量算出来，两者相减不就是最终答案了嘛
所以我们需要把代码稍微修改一下即可：
public int subarraysWithKDistinct(int[] nums, int k) { // // [k, k] = [-∞, k] - [-∞, k - 1] return atMostK(nums, k) - atMostK(nums, k - 1);}// 计算不同整数的个数不超过 k 的子数组private int atMostK(int[] nums, int k) { Map<Integer, Integer> window = new HashMap<>(); int left = 0, right = 0; int ans = 0; while (right < nums.length) { int g = nums[right++]; window.put(g, window.getOrDefault(g, 0) + 1); // 收缩窗口 while (window.size() > k) { int d = nums[left++]; window.put(d, window.get(d) - 1); if (window.get(d) == 0) window.remove(d); } // 更新答案 // 以 nums[right] 结尾的子数组数量 ans += (right - left); } return ans;}