前置
定长
- 定长处理比较容易，不用关心窗口的大小，只用针对满足特定数组的条件进行处理判断。
- 主要的思路如下：
- 窗口右端点在 i 时，由于窗口长度为 k，所以窗口左端点为 i−k+1。
- 三步：入-更新-出。
- 入：下标为 i 的元素进入窗口，更新相关统计量。如果窗口左端点 i−k+1<0，则尚未形成第一个窗口，重复第一步。
- 更新：更新答案。
- 出：下标为 i−k+1 的元素离开窗口，更新相关统计量，为下一个循环做准备。
不定长
不定长滑动窗口主要分为三类：求最长子数组，求最短子数组，求子数组个数。
求最长子数组和最短子数组，还是入——更新——出，三步走。不过会略有不同。
- 更新：下标为 i 的元素进入。如果满足条件，加入，重复，继续扩大，直到遇到不合适情况。
- 出：下标为 left 的元素离开窗口，left++ ，记录此时带窗口大小 i-left+1，为下一个循环做准备。
求子数组个数
- 越短越合法 一般要写 ans += right - left + 1。内层循环结束后，[left, right] 这个子数组是满足题目要求的。由于子数组越短，越能满足题目要求，所以除了 [left, right]，还有 [left+1, right],[left+2, right],…,[right, right] 都是满足要求的。也就是说，当右端点固定在 right 时，左端点在 left, left+1, left+2,…, right 的所有子数组都是满足要求的，这一共有 right−left+1 个。
- 越长越合法 一般要写 ans += left。内层循环结束后，[left, right] 这个子数组是不满足题目要求的，但在退出循环之前的最后一轮循环，[left−1, right] 是满足题目要求的。由于子数组越长，越能满足题目要求，所以除了 [left−1, right]，还有 [left−2, right],[left−3, right],…,[0, right] 都是满足要求的。也就是说，当右端点固定在 right 时，左端点在 0,1,2,…, left−1 的所有子数组都是满足要求的，这一共有 left 个。我们关注的是 left−1 的合法性，而不是 left。
恰好型滑动
| 维度 | （至多≤） | （至少≥） | |
|---|---|---|---|
| 函数目标 | 统计和≤x 的子数组数 | 统计和≥x 的子数组数 | |
| 相减逻辑 | 用 “相邻小范围” 抠除（k 和 k-1） | 用 “相邻大范围” 抠除（k 和 k+1） | |
| 窗口收缩条件 | sum > x（保证窗口内 sum≤x） | sum ≥x（收缩到 sum<x） | |
| 计数方式 | ans += r-l+1（窗口长度） | ans += l（左边界位置） | |
| 核心逻辑 | 正向：直接统计≤x | 反向：统计≥x |
记录
定长处理
- 套用之前所给的解题思路即可，按照入—更新—出，标准三步就行。
- 同样思路，只不过从子数组中的元音字母个数改成了平均数。
力扣： 1343. 大小为 K 且平均值大于等于阈值的子数组数目
- 本题只是对643 题求取的结果进行了筛选
- 与 1456 相似，遇到 w，进入窗口，然后更新，出窗口，最后返回最小值。
- 与 1343 相似，从大于等于阈值的数变成最大而已。
- 变式，要求我们子数组中的元素不相同，且求取最大值。题643 加上附加条件。之前我们一般使用变量来存储信息，本体改用 map 存储。我们对 key 的 value 进行入——更新——出的操作。（注意 map 的操作方法）
- 题643变式，逆向思维。我们求拿去之后剩下子数组的最小和。再用最大和减去即可。
- 题 2461 变式，加上阅读理解干扰。
- 如果我们仿照 2461 题，大概的结果如下，但结果是不对的。
- 原因是：>m 的c在未来要离开窗口，但由于已经丢弃，不能在后续离开窗口时修改，否则会破坏数组索引连续性，导致窗口边界无法准确定位。因此改用“虚拟标记”实现软删除：被丢弃的元素仅标记为特定值（如0），后续统计频率或处理窗口滑动时，只要碰到该标记就判定为无效元素，不纳入频率计算。
class Solution {
public int minArrivalsToDiscard(int[] arrivals, int w, int m) {
int ans = 0；
Map<Integer,Integer> map = new HashMap<>();
int n = arrivals.length;
for(int i = 1 ;i < n;i++){
int left = i-w + 1;
map.merge(arrivals[i],1,Integer::sum);
if(i - w + 1< 0){
continue;
}
if(map.getOrDefault(num, 0) > m){
idx++;
//这里有问题
int c = map.getOrDefault(num, 0);
if(c > 1){
map.put(num,c-1);
}else{
map.remove(num);
}
}
int out = arrivals[left];
int c = map.getOrDefault(out, 0);
if(c > m) {
idx--;
}
if(c > 1){
map.put(out,c-1);
}else{
map.remove(out);
}
}
return ans;
}
}
//正确思路
class Solution {
public int minArrivalsToDiscard(int[] arrivals, int w, int m) {
Map<Integer, Integer> cnt = new HashMap<>();
int ans = 0;
for (int i = 0; i < arrivals.length; i++) {
int x = arrivals[i];
// x 进入窗口
int c = cnt.getOrDefault(x, 0);
if (c == m) { // x 的个数已达上限
// 注意 x 在未来要离开窗口，但由于已经丢弃，不能在离开窗口时修改 cnt
// 这里直接置为 0，未来离开窗口就是 cnt[0]--，不影响答案
arrivals[i] = 0; // 丢弃 arrivals[i]
ans++;
} else {
cnt.put(x, c + 1);
}
// 左端点元素离开窗口，为下一个循环做准备
int left = i + 1 - w;
if (left >= 0) {
cnt.merge(arrivals[left], -1, Integer::sum); // cnt[arrivals[left]]--
}
}
return ans;
}
}
力扣： 1052. 爱生气的书店老板
- 阅读理解+题 643 变式。
- 我们先求出在不生气是时间段的顾客数量，再把那时的顾客数量变为零，那么问题就转化为求一个窗口内最大数的问题了。有点和 3679 相似，本事给的数组也是可以利用的条件，可以用它来简化逻辑。
- 抽象思维+题 643 变式+阅读理解
- 用一个数组记录其中有几个空闲时间段，求合并这些空闲时间段的最大数，又因为题目要求，这些空闲空闲时间段必然是连续合并，所以可以看成滑动窗口。
- 观察题目。题目就转化成了，有n+1 个空余时间段（空闲时间段可以为 0），合并其中连续 k+1 个空余时间段，得到的最大长度是多少
不定长
求最长
- 力扣：3. 无重复字符的最长子串
- 有点类似题 2461 变式，都是要求不重复的，不过字符用数组记录就行了。余下的按照正常的不定长处理方法就可以了。
class Solution {
public int lengthOfLongestSubstring(String s) {
char[] S = s.toCharArray();
int ans = 0;
int left = 0;
int[] cnt = new int[128];
for(int i = 0; i < S.length;i++){
char c = S[i];
cnt[c]++;
while(cnt[c] > 1){
cnt[S[left]]--;
left++;
}
ans = Math.max(ans,i-left+1);
}
return ans;
}
}
- 同第题 3一样，不过由>1 变成 >2
- 题 3 稍微变式，换种角度来开就是，我们只用记录 0 个数即可，当 0 个数>2 时，滑动窗口就行。
- 类似题 1423，逆向思维+排序。
- 排序之后，我们所求子数组很简单，找到其最大元素是最小元素 k 倍的最长那一个数组就行了。又因为排序，可以利用最大元素是最小元素 k 倍进行左移动和找到最大的范围（ps：不需要右指针移动，因为排序，左指针移动整体结果一定是增大的）
力扣： 1208. 尽可能使字符串相等
- 题 643 不定长的一个变式，换种角度看，就是给定一个数组，求其值满足 target 的最长子数组。
力扣：904. 水果成篮
- 阅读理解+题 3 变式。我们只需要求一个只包含两个不同数的最长子数组即可。
力扣： 1695. 删除子数组的最大得分
- 题 3 变式，变化了一下，不用求 i-left+1 最大了，直接不同元素的最大子数组和即可。
- 题 3 变式，由 1 变成 k
- 阅读理解+题 1943 变式，算两次，一次求包含最少T 最长子数组，一次求 F。两者取更大。
- 题 2024 简单化了，只用算一次了，求一次求包含最少 0 的最长子数组
- 题 3 变式，一个变两个。本题关键在于元素的更新处理，我们需要的只是在它不相同的时候递增 left 即可。（注意 i 的起始范围）
- 阅读理解+排序+转换
- 找最长的连续子数组，其最大值减最小值 ≤2k。由于排序后数组是有序的，相当于子数组的最后一个数减去子数组的第一个数 ≤2k。（ps：思维游戏）
class Solution {
public int maximumBeauty(int[] nums, int k) {
Arrays.sort(nums);
int ans = 0;
int left = 0;
for (int i = 0; i < nums.length; i++) {
while (nums[i] - nums[left] > 2*k) {
left++;
}
ans = Math.max(ans,i-left+1);
}
return ans;
}
}
- 力扣： 1658. 将 x 减到 0 的最小操作数
- 逆向思维+题 1695 变式。
求最短
力扣： 209. 长度最小的子数组
- 题 1695 变式，Max 换 min
- 题 3039 变式+元素处理。不考虑字典序的话基本差不多即 1 的个数>k。（ps: 感觉这种没啥办法，调库记忆处理方式）
求子数组个数
越短越合法
- 与之前的差不多，只不过最后的 max/min 。ans +=i-left+1;
class Solution {
public int numSubarrayProductLessThanK(int[] nums, int k) {
if(k<=1){
return 0;
}
int ans =0;
int left= 0;
int cnt =1;
for(int i =0; i<nums.length;i++){
cnt *= nums[i];
while(cnt >=k ){
cnt /= nums[left];
left++;
}
ans +=i-left+1;
}
return ans;
}
}
- 力扣：3258. 统计满足 K 约束的子字符串数量 I
- 题 713 变式。（ps：元素处理小技巧）
int[] cnt = new int[2];
cnt[nums[left] & 1]--;
- 阅读理解+题 713 变式。包装了一下而已，其他不变。
越长越合法
- 和越短越合法的基本没区别。ans += left。
class Solution {
public int numberOfSubstrings(String s) {
char[] S = s.toCharArray();
int ans = 0;
int left = 0;
Map<Character, Integer> map = new HashMap<>();
map.put('a', 0);
map.put('b', 0);
map.put('c', 0);
for (int i = 0; i < S.length; i++) {
map.merge(S[i], 1, Integer::sum);
while (map.get('a') > 0 && map.get('b') > 0 && map.get('c') > 0) {
map.put(S[left], map.get(S[left]) - 1);
left++;
}
ans += left;
}
return ans;
}
}
- 题 1358 变式，基本一样>0 变成>k
恰好型滑动窗口
- 算两次相减即可。