滑动窗口是面试中经常出现的题型，通过上次的分析大家应该都了解了它的出题规律跟解题思想，一般要我们在一个数组或者链表中对一段连续的子集做些什么操作或者计算的时候，这就是在暗示我们用滑动窗口的思想来解决问题，还不了解滑动窗口的同学可以看这里：解析滑动窗口。
但是有些题型可能暗示得那么明显，需要我们灵活地转换一下，而且我在上文结尾的时候也说了，窗口的大小也不一定都是固定的，有时候根据题目条件我们需要动态地扩大或缩小窗口的大小。对于刚入门得同学来说，这就让人很疑惑，今天我就用一道题目来帮助大家对此有一个清晰的认识。
题目如下：假设我们有一个由小写字母构成的字符串，我们可以以大小不超过K的同一种字母替换字符串里的其他字母，使得字符串里出现只包含一种字母的子字符串，找出其中在替换后形成的最长的只包含一种字母的子字符串的长度。
咋一看，这个问题毫无头绪，无从下手。我们稍稍分析一下，拿到一个字符串S1，我们最多只能改变K个字符，这个数目是不变的，为了最大必须替换最多，要想得到最长的结果，我们只能尽量在字符串中找到一个范围，在这个范围内不用执行替换操作，重复字符就很多，假设这个重复字符为C1，然后范围内不相同的字符用C1来替换，然后我们要在努力保证这个范围尽可能包含更多的C1的同时，还要努力控制其中的非C1的字符数目只有K个，这样才有可能是我们想要的结果。
那其实我们就要维护一个不相同字符不超过K个的范围，题目也就转换成了给定一个字符串，找到它的一个连续范围，这些范围内最多包含K个不相同的字符，返回其中最长子串的长度。提到范围我们是可以联想到窗口的，而且计算给定字符串的某个符合条件的连续范围的长度好像挺符合我们文章开头对滑动窗口问题的定义啊！但是这个窗口大小我们没办法确定啊，这该如何是好！看样子我们只会做我们之前熟悉的题目啊！
别急，我们再仔细观察一下转换后的题目，跟前文中的子数组平均数的题目做个比较，我们发现他们都有K 个元素的限制啊！这可真是好消息，在前文中我们窗口大小不到K时就一直往窗口中添加元素，达到K时再踢出元素，这里我们只要不相等字符数目不超过K就一直添加元素不就好啦！我在前文中也跟大家提到过，我们不可能接触所有的题目了，做题要真正理解题目跟解题思路，把不熟悉的题目尽力转换成自己熟悉的题目，此时此刻，我们应该可以说是把这道题目变得“熟悉”了。
好了，知道了突破口，我们整理下详细的解题步骤：
维护一个窗口，使用循环迭代这个字符串，每次尽可能向窗口里添加一个字符，这样子串就能尽力变长；
变长是有约束的，随着窗口范围变大，新字符的加入，重复数量的字符可能就会产生变化(比如由aabb->aabbb，数目最多的字符从a变成了b)，为了追踪重复数量最多的字符，我们使用HashMap来保存已添加的字符的数量，当然了，数组也是可以的，毕竟只有26个字母；
我们知道已迭代字符的数量，知道重复最多的字符的数量，就能知道需要替换的字符的数量，如果这个数量超过K，我们就需要缩小我们的窗口了。
把这些步骤写下来，我们的代码实现就很容易写出来了：
public static int findLength(String str, int k) {
int windowStart = 0, maxLength = 0, maxRepeatLetterCount = 0;
Map<Character, Integer> letterFrequencyMap = new HashMap<>();
// 尝试扩大[windowStart, windowEnd]的范围
for (int windowEnd = 0; windowEnd < str.length(); windowEnd++) {
char rightChar = str.charAt(windowEnd);
letterFrequencyMap.put(rightChar, letterFrequencyMap.getOrDefault(rightChar, 0) + 1);
maxRepeatLetterCount = Math.max(maxRepeatLetterCount, letterFrequencyMap.get(rightChar));
// 窗口大小减去最大重复字符的数目即可得到要替换的字符的数目
if (windowEnd - windowStart + 1 - maxRepeatLetterCount > k) {
char leftChar = str.charAt(windowStart);
letterFrequencyMap.put(leftChar, letterFrequencyMap.get(leftChar) - 1);
windowStart++;
}
maxLength = Math.max(maxLength, windowEnd - windowStart + 1);
}
return maxLength;
}
由于我们只执行了一次循环，这个算法的时间复杂度只有O(n)，而由于我们字母只有26个，所以我们的HashMap恒定的只会保存最多26个字母的数目，我们可以认为此时的空间复杂度是O(1)，这算是一个比较好的结果了。
通过这道题，相信大家都能对滑动窗口有更深层的了解，其实动态滑动窗口也就这么回事儿，以后再遇到滑动窗口的题目肯定也会知道该怎么变通跟转换了。我们主要通过两个变量来维护窗口，其实这在算法中，也是一种重要的解题技巧叫做双指针。下次，我会带大家探讨一下双指针的妙用
网友评论