大家好，我是 方圆。在我刷了一些滑动窗口相关的题目之后，发现很有技巧性，只要掌握了解题思路，就会很简单，所以我决定用这篇帖子记录一下，也帮助同样在刷滑动窗口相关题目的同学。
使用滑动窗口解决的问题一般会有 连续子数组 和 子串 关键信息，我将滑动窗口题目分成两大类：固定窗口 和 动态窗口 问题。前者比较简单，循环维护满足规定大小的窗口即可；后者还能进行细分，分为最大窗口问题和最小窗口问题。最大窗口需要在满足条件的情况下尽可能地扩大 right 指针的值，让窗口尽可能大，最小窗口则是在满足条件的基础上，不断地缩小窗口，让窗口尽可能的小。以上我认为就能将所有滑动窗口问题全部涵盖在内了，大家可以根据自己感兴趣的部分选择性阅读，读完之后推荐做一下相关题目来加深对滑动窗口的理解。如果大家想要找刷题路线的话，可以参考 Github: LeetCode。
固定窗口
在滑动窗口类型的题目中，固定窗口大小的问题是最简单的，我认为它遵循着下面这种模式：
int left = 0, right = 0;
while (right < nums.length) {
// 相关变量赋值操作
// 如果在符合窗口大小的情况下进行题解判断
if (right - left + 1 == windowLength) {
// 判断是否符合题解，符合条件则记录答案
// 窗口缩小，将 left 指针处的元素移除
left++;
}
// 窗口右移
right++;
}
窗口移动过程中不断扩大，直到满足窗口大小，进行相关逻辑处理，处理完之后把窗口 left 指针处元素移除，缩小窗口，下次再进入循环时，将再次满足指定窗口大小。
下面是一些相关的练习，大家可以做一下，掌握思路之后比较简单：
相关练习
- 438. 找到字符串中所有字母异位词
public List findAnagrams(String s, String p) {
List res = new ArrayList();
int[] mark = new int[26];
for (char c : p.toCharArray()) {
mark[c - 'a']++;
}
int needCount = p.length();
int left = 0, right = 0;
while (right 0) {
needCount--;
}
mark[index]--;
if (right - left + 1 == p.length()) {
if (needCount == 0) {
res.add(left);
}
int leftIndex = s.charAt(left) - 'a';
if (mark[leftIndex] >= 0) {
needCount++;
}
mark[leftIndex]++;
left++;
}
right++;
}
return res;
}
- 567. 字符串的排列
public boolean checkInclusion(String s1, String s2) {
int[] mark = new int[26];
char[] s1CharArray = s1.toCharArray();
for (char c : s1CharArray) {
mark[c - 'a']++;
}
int needCount = s1.length();
int left = 0, right = 0;
while (right 0) {
needCount--;
}
mark[rightIndex]--;
if (right - left + 1 == s1.length()) {
if (needCount == 0) {
return true;
}
int leftIndex = s2.charAt(left) - 'a';
if (mark[leftIndex] >= 0) {
needCount++;
}
mark[leftIndex]++;
left++;
}
right++;
}
return false;
}
- 1052. 爱生气的书店老板
这道题的技巧很有意思，我们一起看一下。根据题意可知，老板在不生气的时候，顾客是不变的，而且不生气的状态也不会变成生气，所以我们可以先把能确定的顾客累加计算起来，并把这些累加过的顾客置为零。之后我们维护一个大小为 minutes 的窗口滑动，统计在该固定窗口下能留下的顾客的最大值就是我们能够最多留下的顾客了，最后不生气下的顾客和生气时能留下的最多的顾客即为所求：
public int maxSatisfied(int[] customers, int[] grumpy, int minutes) {
int already = 0;
for (int i = 0; i < customers.length; i++) {
if (grumpy[i] == 0) {
already += customers[i];
customers[i] = 0;
}
}
int max = 0;
int sum = 0;
int left = 0, right = 0;
while (right < customers.length) {
sum += customers[right];
if (right - left + 1 == minutes) {
max = Math.max(max, sum);
sum -= customers[left++];
}
right++;
}
return already + max;
}
动态窗口
我认为动态窗口问题可以归为两类，分别是求 最小窗口 和求 最大窗口 问题，我们先来看下解题思路的模板，注意其中的注释信息：
- 求最小窗口的模板如下：
int left = 0, right = 0;
while(right < nums.length) {
// 当前元素进入窗口，计算窗口相关值的变化
doSomething();
// 求最小窗口：在满足条件的情况下，不断地缩小窗口，即 left 右移
while(condition && left
