算法总结之滑动窗口
前言
滑动窗口类问题是面试当中的高频题，问题本身其实并不复杂，但是实现起来细节思考非常的多，想着想着可能因为变量变化，指针移动等等问题，导致程序反复删来改去，有思路，但是程序写不出是这类问题最大的障碍。
本文会将 LeetCode 里面的大部分滑动窗口问题分析、总结、分类，并提供一个可以参考的模版
问题形式
滑动窗口这类问题一般需要用到双指针来进行求解，另外一类比较特殊则是需要用到特定的数据结构，如 Map，队列等。
题目问法大致有这几种
1. 给两个字符串，一长一短，问其中短的是否在长的中满足一定的条件存在
- 求长的的最短子串，该子串必须涵盖短的的所有字符
- 短串的某种排列在长的中出现的所有位置
2. 给一个字符串或者数组，问这个字符串的子串或者子数组是否满足一定的条件
- 含有少于 k k k 个不同字符的最长子串
- 所有字符都只出现一次的最长子串
除此之外，还有一些其他的问法，但是不变的是，这类题目脱离不开主串（主数组）和子串（子数组）的关系，要求的时间复杂度往往是 O ( N ) O(N) O(N) ，空间复杂度往往是 O ( 1 ) O(1) O(1) 的。
解题思路与模板
根据前面的描述，滑动窗口就是这类题目的重点，换句话说，窗口的移动就是重点！我们要控制前后指针的移动来控制窗口，这样的移动是有条件的，也就是要想清楚在什么情况下移动，在什么情况下保持不变。
思路是保证右指针每次往前移动一格，每次移动都会有新的一个元素进入窗口，这时条件可能就会发生改变，然后根据当前条件来决定左指针是否移动，以及移动多少格。
/** 参考模板 */
slidingWindow(char[] s) {
// 申请一个散列，用于记录窗口中具体元素的个数情况
// 这里用数组的形式呈现，也可以考虑其他数据结构
int[] hash = new int[...];
// 预处理（可省略）, 一般情况是初始化 hash 内容
...
// left 为窗口左指针，right 为窗口右指针
// count 记录题目要求记录某些中间结果（最多最少等值）
// result 记录结果
int left = 0, count = 0, result = 0;
for (int right = 0; right < s.length; right++) {
// 更新新元素在散列中的数量
hash[s[right]]++;
// 根据窗口的变更结果来改变条件值
if (hash[s[right]] == ...) {
count++;
}
// 如果当前窗口条件不满足，移动左指针直至满足窗口为止
while (...) {
hash[s[left]]--;
// 视情况改变记录的中间结果
if (...) {
count--;
}
left++;
}
// 更新结果
result = ...
}
}
具体问题
无重复字符的最长子串
给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。
示例
输入："abcabcbb"
输出：3
解释：因为无重复字符的最长子串是 "abc"，所以其长度为 3。
解题思路
输入只有一个字符串，要求子串里面不能够有重复的元素，这里 count 都不需要定义，直接判断哈希散列里面的元素是不是在窗口内即可，是的话得移动左指针去重。
建立一个 128 位大小的整型数组，用来建立字符和其出现位置之间的映射。维护一个滑动窗口，窗口内的都是没有重复的字符，去尽可能的扩大窗口的大小，窗口不停的向右滑动。
public int lengthOfLongestSubstring(String s) {
if (s == null || s.isEmpty()) return 0;
char[] sArr = s.toCharArray();
int[] hash = new int[128];
int left = 0, result = Integer.MIN_VALUE;
for (int right = 0; right < sArr.length; right++) {
// 如果当前遍历到的字符从未出现过，那么直接扩大右边界
hash[sArr[right]]++;
// 如果当前遍历到的字符出现过，则缩小窗口（左指针向右移动）
while (hash[sArr[right]] != 1) {
hash[sArr[left]]--;
left++;
}
// 更新结果
result = Math.max(result, right - left + 1);
}
return result;
}
替换后的最长重复字符
给你一个仅由大写英文字母组成的字符串，你可以将任意位置上的字符替换成另外的字符，总共可最多替换 k 次。在执行上述操作后，找到包含重复字母的最长子串的长度。
示例
输入：s = "ABAB", k = 2
输出：4
解释：用两个'A'替换为两个'B',反之亦然。
解题思路
最简单的方法就是把哈希散列遍历一边找到最大的字符数量，但是仔细想想如果我们每次新进元素都更新这个最大数量，且只更新一次，我们保存的是当前遍历过的全局的最大值，它肯定是比实际的最大值大的，我们左指针移动的条件是 right - left + 1 - count > k，保存的结果是 result = Math.max(result, right - left + 1)； 这里 count 比实际偏大的话，虽然导致左指针不能移动，但是不会记录当前的结果，所以最后的答案并不会受影响。
public int characterReplacement(String s, int k) {
if (s == null || s.isEmpty()) return 0;
char[] sArr = s.toCharArray();
// 仅含大写英文字母，设为26即可
int[] hash = new int[26];
// count记录最大出现次数
int left = 0, count = 0, result = 0;
for (int right = 0; right < sArr.length; right++) {
// 调整字母在hash中的索引位置
hash[sArr[right] - 'A']++;
// 比较最大数字符数和当前字符的数量
count = Math.max(count, hash[sArr[right] - 'A']);
// 子字符串的长度减去出现次数最多的字符个数大于k则移动左指针
while (right - left + 1 - count > k) {
hash[sArr[left] - 'A']--;
left++;
}
result = Math.max(result, right - left + 1);
}
return result;
}
长度为 K 的无重复字符子串
给你一个字符串 S，找出所有长度为 K 且不含重复字符的子串，请你返回全部满足要求的子串的数目。
示例
输入：S = "havefunonleetcode", K = 5
输出：6
解释：这里有 6 个满足题意的子串，分别是
'havef','avefu','vefun','efuno','etcod','tcode'
解题思路
根据题意我们发现相当于窗口大小固定为K，同时在窗口内必须没有重复的字符。我们用左右指针可以计算出当前窗口的大小right - left + 1，同时再利用一个count对字符种类进行计数（也可以直接用一个boolean值即可），那么很容易可以得出当right - left + 1 > K 或者 count > 0时需要移动左指针了。剩下的部分就是愉快地套用模板啦。
public int numKLenSubstrNoRepeats(String S, int K) {
if (S == null || S.length() < K) return 0;
char[] sArr = S.toCharArray();
int[] hash = new int[128];
int left = 0, count = 0, result = 0;
for (int right = 0; right < sArr.length; right++) {
hash[sArr[right]]++;
// 若更新hash后大于1，说明出现了重复种类的字符，count加1
if (hash[sArr[right]] > 1) {
count++;
}
// 当子串超过窗口大小，或者窗口内包含重复字符时，移动左指针
while (left < right && (right - left + 1 > K || count > 0)) {
// 更新左指针右移后字符数量
hash[sArr[left]]--;
// 若更新后该字符数量仍大于0，说明找到了重复的字符
// 此时将count减1
if (hash[sArr[left]] > 0) {
count--;
}
left++;
}
// 更新结果，此时子串刚好满足窗口条件，结果加1，同时将count重置
if (right - left + 1 == K) {
result++;
count = 0;
}
}
return result;
}
至多包含两个不同字符的最长子串
给定一个字符串 s ，找出至多包含两个不同字符的最长子串 t 。
示例
输入："ccaabbb"
输出：5
解释： t 是 "aabbb"，长度为5
解题思路
类似于上一题，不过我们用count来记录当前窗口内字符的种类数量，当出现新字符以及滑动左指针时，做相应的判断来改变count，窗口大小始终保持在满足条件至多两个不同字符的情况下。
public int lengthOfLongestSubstringTwoDistinct(String s) {
if (s == null || s.isEmpty()) return 0;
char[] sArr = s.toCharArray();
int[] hash = new int[128];
// count记录出现过的不同种类字符的数量
int left = 0, count = 0, result = Integer.MIN_VALUE;
for (int right = 0; right < sArr.length; right++) {
hash[sArr[right]]++;
// 若当前字符在hash中计数为1，说明是前面未出现过的，count加1
if (hash[sArr[right]] == 1) {
count++;
}
// 若种类超过2了，需要将左指针右移，以满足窗口的条件
while (count > 2) {
// 更新左指针右移后字符数量
hash[sArr[left]]--;
// 若更新后该字符数量为0，说明当前窗口只含有一个该类字符
// 则种类数量count相应要减1
if (hash[sArr[left]] == 0) {
count--;
}
left++;
}
// 更新结果
result = Math.max(result, right - left + 1);
}
return result;
}
至多包含 K 个不同字符的最长子串
给定一个字符串 s ，找出 至多 包含 k 个不同字符的最长子串 T。
示例
输入： s = "eceba", k = 2
输出：3
解释： 则 T 为 "ece"，所以长度为 3。
解题思路
和上一题完全一样的思路，只需要把判断窗口条件的地方改成 count > k ，又一题困难被我们直接秒杀。
public int lengthOfLongestSubstringKDistinct(String s, int k) {
if (s == null || s.isEmpty()) return 0;
char[] sArr = s.toCharArray();
int[] hash = new int[128];
int left = 0, count = 0, result = Integer.MIN_VALUE;
for (int right = 0; right < sArr.length; right++) {
hash[sArr[right]]++;
if (hash[sArr[right]] == 1) {
count++;
}
// 此处改为超过k种不同字符则移动左指针
while (count > k) {
hash[sArr[left]]--;
if (hash[sArr[left]] == 0) {
count--;
}
left++;
}
result = Math.max(result, right - left + 1);
}
return result;
}
下面来看看两个字符串的情况
最小覆盖子串
给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字母的最小子串。
示例
输入：S = "ADOBECODEBANC", T = "ABC"
输出："BANC"
解释：S 内包含 T 中所有字母的最小子串为"BANC"
解题思路
同样是两个字符串之间的关系问题，因为题目求的最小子串，也就是窗口的最小长度，说明这里的窗口大小是可变的，这里移动左指针的条件变成，只要左指针指向不需要的字符，就进行移动。
public String minWindow(String s, String t) {
if (s == null || t == null || s.length() < t.length()) return "";
char[] sArr = s.toCharArray(), tArr = t.toCharArray();
// 记录字符出现次数
int[] hash = new int[128];
// 以T中的字符初始化hash内字符数量
for (char c : tArr) {
hash[c]++;
}
// count 记录匹配字符数，minLen 记录最小子串长度
String result = "";
int left = 0, count = 0, minLen = Integer.MAX_VALUE;
for (int right = 0; right < sArr.length; right++) {
// 更新S中字符在散列中的数量
hash[sArr[right]]--;
// 若经过上一步减1后仍大于等于0
// 说明S中的该字符在T中出现过（因为我们用T中字符数量初始化了hash），匹配数加1
if (hash[sArr[right]] >= 0) {
count++;
}
// 若某字符在hash中为负，说明在S中出现过，在T中未出现，略过，不需要匹配
while (left < right && hash[sArr[left]] < 0) {
hash[sArr[left]]++;
left++;
}
// 更新结果
// count == tArr.length说明找到了T中所有字符
if (count == tArr.length && minLen > right - left + 1) {
minLen = right - left + 1;
result = s.substring(left, right + 1);
}
}
return result;
}
字符串的排列
给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。
示例
输入：s1 = "ab" s2 = "eidbaooo"
输出：True
解释：s2 包含 s1 的排列之一 ("ba").
解题思路
首先窗口是固定的，窗口长度就是s1的长度，也就是说，右指针移动到某个位置后，左指针必须跟着一同移动，且每次移动都是一格，count 用来记录窗口内满足条件的元素，直到 count 和窗口长度相等即可。
public boolean checkInclusion(String s1, String s2) {
if (s1.length() > s2.length()) return false;
char[] arr1 = s1.toCharArray(), arr2 = s2.toCharArray();
int[] hash = new int[128];
// 以s1中的字符初始化hash内字符数量
for (char c : arr1) {
hash[c]++;
}
// count 记录匹配字符数，size 表示窗口的大小
int left = 0, count = 0, size = arr1.length;
for (int right = 0; right < arr2.length; right++) {
// 更新s2字符在散列中的数量
hash[arr2[right]]--;
// 说明s2中的该字符在s1中出现过
if (hash[arr2[right]] >= 0) {
count++;
}
// 右指针移动到超过窗口大小时，左指针跟着移动
if (right > size - 1) {
hash[arr2[left]]++;
// 若当前是已经匹配上的字符，左移后会丢失匹配，故匹配数减1
if (hash[arr2[left]] > 0) {
count--;
}
left++;
}
// 更新结果，count == size 表示匹配字符满足窗口大小
if (count == size) {
return true;
}
}
return false;
}
找到字符串中所有字母异位词
给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。字符串只包含小写英文字母，并且字符串 s 和 p 的长度都不超过 20100。
示例
输入：s: "cbaebabacd" p: "abc"
输出：[0, 6]
解释：
起始索引等于 0 的子串是 "cba", 它是 "abc" 的字母异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的字母异位词。
解题思路
和上一题完全一致的思路，窗口固定为p串的长度。
public List<Integer> findAnagrams(String s, String t) {
if (s == null || t == null || s.length() < t.length()) return new ArrayList<Integer>();
char[] sArr = s.toCharArray(), tArr = t.toCharArray();
// 仅含小写英文字母，设为26即可
int[] hash = new int[26];
for (char c : tArr) {
hash[c - 'a']++;
}
// count 记录匹配字符数，size 表示窗口的大小
int left = 0, count = 0, size = tArr.length;
List<Integer> result = new ArrayList<>();
for (int right = 0; right < sArr.length; right++) {
// 更新s中的字符在散列中的数量
hash[sArr[right] - 'a']--;
// 说明s中的该字符在t中出现过
if (hash[sArr[right] - 'a'] >= 0) {
count++;
}
if (right > size - 1) {
hash[sArr[left] - 'a']++;
if (hash[sArr[left] - 'a'] > 0) {
count--;
}
left++;
}
// 更新结果，记录子串起始位置
if (count == size) {
result.add(left);
}
}
return result;
}
最后来看看数组类型的题吧
最大连续1的个数 III
给定一个由若干 0 和 1 组成的数组 A，我们最多可以将 K 个值从 0 变成 1 。返回仅包含 1 的最长（连续）子数组的长度。
示例
输入：A = [1,1,1,0,0,0,1,1,1,1,0], K = 2
输出：6
解释：[1,1,1,0,0,1,1,1,1,1,1]
解题思路
这题有点像上面的 替换后的最长重复字符，只不过把字符串换成了数组，由于只有两种数字 0 和 1，并且只求连续 1 的长度，我们可以连 hash 映射都不需要了，直接计算遍历到的 0 的个数即可。
public int longestOnes(int[] A, int K) {
if (A == null) return 0;
int left = 0, count = 0, result = 0;
for (int right = 0; right < A.length; right++) {
// 找到了0需要替换，count加1
if (A[right] == 0) {
count++;
}
while (count > K) {
// 之前的0滑出了窗口，count减1
if (A[left] == 0) {
count--;
}
left++;
}
result = Math.max(result, right - left + 1);
}
return result;
}
K 个不同整数的子数组
给定一个正整数数组 A，如果 A 的某个子数组中不同整数的个数恰好为 K，则称 A 的这个连续、不一定独立的子数组为好子数组。
示例
输入：A = [1,2,1,2,3], K = 2
输出：7
解释：恰好由 2 个不同整数组成的子数组
[1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2]
解题思路
这题比较 tricky 的一个地方在于，这里不是求最小值最大值，而是要你计数。
但是如果每次仅仅加 1 的话又不太对，例如 A = [1,2,1,2,3], K = 2 这个例子，假如右指针移到 index 为 3 的位置，如果按之前的思路左指针根据 count 来移动，当前窗口是 [1,2,1,2]，但是怎么把 [2,1] 给考虑进去呢？
可以从数组和子数组的关系来思考！
假如 [1,2,1,2] 是符合条件的数组，如果要计数的话，[1,2,1,2] 要求的结果是否和 [1,2,1] 的结果存在联系？这两个数组的区别在于多了一个新进来的元素，之前子数组计数没考虑到这个元素，假如把这个元素放到之前符合条件的子数组中组成的新数组也是符合条件的，我们看看这个例子中所有满足条件的窗口以及对应的满足条件的子数组情况：
[1,2,1,2,3] // 窗口满足条件
l r // 满足条件的子数组 [1,2]
[1,2,1,2,3] // 窗口满足条件
l r // 满足条件的子数组 [1,2],[2,1],[1,2,1]
[1,2,1,2,3] // 窗口满足条件
l r // 满足条件的子数组 [1,2],[2,1],[1,2,1],[1,2],[2,1,2],[1,2,1,2]
[1,2,1,2,3] // 窗口不满足条件，移动左指针至满足条件
l r
[1,2,1,2,3] // 窗口满足条件
l r // 满足条件的子数组 [1,2],[2,1],[1,2,1],[1,2],[2,1,2],[1,2,1,2],[2,3]
你可以看到对于一段连续的数组，新的元素进来，窗口增加 1，每次的增量都会在前一次增量的基础上加 1。当新的元素进来打破当前条件会使这个增量从新回到 1，这样我们左指针移动条件就是只要是移动不会改变条件，就移动，不然就停止。
public int subarraysWithKDistinct(int[] A, int K) {
if (A == null || A.length < K) return 0;
// hash表示A中元素出现次数，因为条件中1 <= A[i] <= A.length
int[] hash = new int[A.length + 1];
// kind表示出现过的元素种类
// count表示子数组的计数
int left = 0, kind = 0, count = 1, result = 0;
for (int right = 0; right < A.length; right++) {
// 如果当前遍历到的元素从未出现过，那么直接扩大右边界
hash[A[right]]++;
// 当前元素是第一次出现，种类加1
if (hash[A[right]] == 1) {
kind++;
}
// 左指针右移直至窗口满足条件
while (hash[A[left]] > 1 || kind > K) {
hash[A[left]]--;
if (kind > K) {
count = 1;
kind--;
} else {
count++;
}
left++;
}
if (kind == K) {
result += count;
}
}
return result;
}
总结
至此，本文用同一个框架解决了多道滑动窗口的题目，这类问题思维复杂度并不高，但是出错点往往在细节。记忆常用的解题模版还是很有必要的，特别是对于这种变量名多，容易混淆的题型。有了这个框架，思考的点就转化为 “什么条件下移动左指针”，无关信息少了，思考加实现自然不是问题。
