友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
Sliding Window 滑动窗口
滑动窗口类型的题目经常是用来执行数组或是链表上某个区间（窗口）上的操作。比如找最长的全为1的子数组长度。滑动窗口一般从第一个元素开始，一直往右边一个一个元素挪动。当然了，根据题目要求，我们可能有固定窗口大小的情况，也有窗口的大小变化的情况。
下面是一些我们用来判断我们可能需要上滑动窗口策略的方法：
-
这个问题的输入是一些线性结构：比如链表呀，数组啊，字符串啊之类的
-
让你去求最长/最短子字符串或是某些特定的长度要求
经典题目：
Maximum Sum Subarray of Size K (easy)
Smallest Subarray with a given sum (easy)
No-repeat Substring (hard)
Longest Substring with Same Letters after Replacement (hard)
Longest Subarray with Ones after Replacement (hard)
整体思路
滑动窗口算法的抽象思想：
// @author D瓜哥 · https://www.diguage.com
int left = 0, right = 0;
while (right < s.size()) {
window.add(s[right]);
right++;
while (valid) {
window.remove(s[left]);
left++;
}
}其中 window 的数据类型可以视具体情况而定，比如上述题目都使用哈希表充当计数器，当然你也可以用一个数组实现同样效果，因为我们只处理英文字母。
稍微麻烦的地方就是这个 valid 条件，为了实现这个条件的实时更新，我们可能会写很多代码。比如前两道题，看起来解法篇幅那么长，实际上思想还是很简单，只是大多数代码都在处理这个问题而已。