当前位置：网站首页>滑动窗口方法
滑动窗口方法
2022-08-02 03:33:00 【EvilChou】
所谓滑动窗口，就是不断的调节子序列的起始位置和终止位置，从而得出我们要想的结果。
在暴力解法中，是一个for循环滑动窗口的起始位置，一个for循环为滑动窗口的终止位置，用两个for循环 完成了一个不断搜索区间的过程。
那么滑动窗口如何用一个for循环来完成这个操作呢。
首先要思考 如果用一个for循环，那么应该表示 滑动窗口的起始位置，还是终止位置。
如果只用一个for循环来表示 滑动窗口的起始位置，那么如何遍历剩下的终止位置？
此时难免再次陷入 暴力解法的怪圈。
所以 只用一个for循环，那么这个循环的索引，一定是表示 滑动窗口的终止位置。
那么问题来了， 滑动窗口的起始位置如何移动呢？
这里以例题来举例：
给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。
示例：
输入：s = 7, nums = [2,3,1,2,4,3] 输出：2 解释：子数组 [4,3] 是该条件下的长度最小的子数组。
来看一下查找的过程：
最后找到 4，3 是最短距离。
其实从动画中可以发现滑动窗口也可以理解为双指针法的一种！只不过这种解法更像是一个窗口的移动，所以叫做滑动窗口更适合一些。
在本题中实现滑动窗口，主要确定如下三点：
- 窗口内是什么？
- 如何移动窗口的起始位置？
- 如何移动窗口的结束位置？
窗口就是 满足其和 ≥ s 的长度最小的连续子数组。
窗口的起始位置如何移动：如果当前窗口的值大于s了，窗口就要向前移动了（也就是该缩小了）。
窗口的结束位置如何移动：窗口的结束位置就是遍历数组的指针，也就是for循环里的索引。
解题的关键在于 窗口的起始位置如何移动
滑动窗口框架(Java)：
/* 滑动窗口算法框架 */
void slidingWindow(string s, string t) {
Map<Character,Integer> need = new HashMap<>();
Map<Character,Integer> window = new HashMap<>();
for (char c : t.toCharArray())
need.put(c,need.getOrDefault(c,0)+1);
int left = 0, right = 0;
int count = 0;
while (right < s.length()) {
// c 是将移入窗口的字符
char c = s.charAt(right);
// 右移窗口
right++;
// 进行窗口内数据的一系列更新
...
// 判断左侧窗口是否要收缩
while (window needs shrink) {
// d 是将移出窗口的字符
char d = s.charAt(left);
// 左移窗口
left++;
// 进行窗口内数据的一系列更新
...
}
}
}一、最小覆盖子串
LeetCode76题
算法思路：
1、我们在字符串 S 中使用双指针中的左右指针技巧，初始化 left = right = 0，把索引左闭右开区间 [left, right) 称为一个「窗口」（左闭右开，保证初始窗口中没有元素）。
2、我们先不断地增加 right 指针扩大窗口 [left, right)，直到窗口中的字符串符合要求（包含了 T 中的所有字符）。
3、此时，我们停止增加 right，转而不断增加 left 指针缩小窗口 [left, right)，直到窗口中的字符串不再符合要求（不包含 T 中的所有字符了）。同时，每次增加 left，我们都要更新一轮结果。
4、重复第 2 和第 3 步，直到 right 到达字符串 S 的尽头。
第 2 步相当于在寻找一个「可行解」，然后第 3 步在优化这个「可行解」，最终找到最优解，也就是最短的覆盖子串。左右指针轮流前进，窗口大小增增减减，窗口不断向右滑动，这就是「滑动窗口」这个名字的来历。
下面画图理解一下，needs 和 window 相当于计数器，分别记录 T 中字符出现次数和「窗口」中的相应字符的出现次数。
初始状态：
增加 right，直到窗口 [left, right) 包含了 T 中所有字符：
现在开始增加 left，缩小窗口 [left, right)。
直到窗口中的字符串不再符合要求，left 不再继续移动。
之后重复上述过程，先移动 right，再移动 left…… 直到 right 指针到达字符串 S 的末端，算法结束。
首先，初始化 window 和 need 两个哈希表，记录窗口中的字符和需要凑齐的字符：
然后，使用 left 和 right 变量初始化窗口的两端，不要忘了，区间 [left, right) 是左闭右开的，所以初始情况下窗口没有包含任何元素：
其中 count 变量表示窗口中满足 need 条件的字符个数，如果 count 和 need.size 的大小相同，则说明窗口已满足条件，已经完全覆盖了串 T。
现在开始套模板，只需要思考以下四个问题：
1、当移动 right 扩大窗口，即加入字符时，应该更新哪些数据？
2、什么条件下，窗口应该暂停扩大，开始移动 left 缩小窗口？
3、当移动 left 缩小窗口，即移出字符时，应该更新哪些数据？
4、我们要的结果应该在扩大窗口时还是缩小窗口时进行更新？
如果一个字符进入窗口，应该增加 window 计数器；如果一个字符将移出窗口的时候，应该减少 window 计数器；当 count 满足 need 时应该收缩窗口；应该在收缩窗口的时候更新最终结果。
下面是完整代码：
class Solution{
public String minWindow(String s, String t){
//哈希表（字典），它的一个方法 containsKey(key) 可以判断键key是否存在。需要注意的是，如果该 key 不存在，创建这个key，并把 map[key] 赋值为 0. map.put(key, map.getOrDefault(key, 0) + 1)。
Map<Character,Integer> need = new HashMap<>(); //need为t字符串中需要的各个字符的个数
Map<Character,Integer> window = new HashMap<>();//window为窗口中t中所需字符的个数
for(char c : t.toCharArray()) //toCharArray()方法，将字符串对象中的字符转换为一个字符数组。 遍历数组，找到t中所需的每个字符
need.put(c,need.getOrDefault(c,0)+1);
int left = 0, right = 0;
int count = 0;//count记录当前窗口中符合need要求的字符的数量,当count == need.size()时即可缩小窗口
int start = 0;//记录所选子串的起始位置
int len = Integer.MAX_VALUE;//len用来记录最终窗口的长度，并且以len作比较，淘汰选出最小的substring的len
//第一次遍历，找出满足条件的子串
while(right < s.length()){
char c = s.charAt(right);
right++;
if(need.containsKey(c)){
window.put(c,window.getOrDefault(c,0)+1);
//java的包装类默认缓存了-128~ +127之间的整数对应的包装类对象，因此这个范围之内可以直接 == 也没问题，Integer 12 = Integer 12；
//但是如果超了这个范围，返回的包装类对象就需要在堆区重新new了，那么 == 在判断的时候判断的时候由于判断的是地址且是new出来的，因此可能 为false；
//总结：包装类比较大小，无脑用equals就可以啦
if(need.get(c).equals(window.get(c))
count++;
}
//第二次 缩小窗口，找符合条件的最小子串
while(count == need.size(){
if(right - left < len){
len = right - left;
start = left;
}
char d = s.charAt(left);
left++;
if(need.containskey(d)){
//window.put(d,window.get(d)-1); 若一进去就将window对应的键值缩小，就永远不会满足下面的if，while也会一直执行，直到left越界
if(need.get(d).equals(window.get(d)){
count--;
}
window.put(d,window.get(d)-1);
}
}
}
return len == Integer.MAX_VALUE ? "" : s.substring(start,start+len);
}
}二、字符串排列
LeetCode567题
这道题的解法，基本上和最小覆盖子串一模一样，只需要改变两个地方：
1、本题移动 left 缩小窗口的时机是窗口大小大于 t.size() 时，应为排列嘛，显然长度应该是一样的。
2、当发现 count == need.size() 时，就说明窗口中就是一个合法的排列，所以立即返回 true。
至于如何处理窗口的扩大和缩小，和最小覆盖子串完全相同。
class Solution{
public boolean checkInclusion(String s1, String s2){
Map<Character,Integer> need = new HashMap<>();
Map<Character,Integer> window = new HashMap<>();
for(char c : s1.toCharArray())
need.put(c,need.getOrDefault(c,0)+1);
int left = 0, right = 0;
int count = 0;
while(right < s2.length()){
char c = s2.charAt(right);
right++;
if(need.containsKey(c)){
window.put(c,window.getOrDefault(c,0)+1);
if(need.get(c).equals(window.get(c)))
count++;
}
while(right - left >= s1.length()){ //定长窗口
if(count == need.size()){
return true;
}
char d = s2.charAt(left);
left++;
if(need.containsKey(d)){
if(need.get(d).equals(window.get(d))){
count--;
}
window.put(d,window.get(d)-1);
}
}
}
return false;
}
}三、找到字符串中所有字母的异位词
LeetCode438题
class Solution{
public List<Integer> findAnagrams(String s, String p){
Map<Character,Integer> need = new HashMap<>();
Map<character,Integer> window = new HashMap<>();
for(char c : p.toCharArray())
need.put(c,need.getOrDefault(c,0)+1);
int left = 0, right = 0;
int count = 0;
List<Integer> res = new ArrayList<>(); //ArrayList 类是一个可以动态修改的数组，与普通数组的区别就是它是没有固定大小的限制，我们可以添加或删除元素。
//ArrayList 继承了 AbstractList ，并实现了 List 接口
while(right < s.length()){
char c = s.charAt(right);
right++;
if(need.containsKey(c)){
window.put(c,window.getOrDefault(c,0)+1);
if(need.get(c).equals(window.get(c)))
count++;
}
while(right - left >= p.length()){ //定长窗口
if(count == need.size()){
res.add(left);
}
char d = s.charAt(left);
left++;
if(need.containsKey(d)){
if(need.get(d).equals(window.get(d))){
count--;
}
window.put(d,window.get(d)-1);
}
}
}
return res;
}
}四、最长无重复子串
LeetCode第3题
这就是变简单了，连 need 和 count 都不需要，而且更新窗口内数据也只需要简单的更新计数器 window 即可。
当 window.get(c) 值大于 1 时，说明窗口中存在重复字符，不符合条件，就该移动 left 缩小窗口了嘛。
唯一需要注意的是，在哪里更新结果 res 呢？我们要的是最长无重复子串，哪一个阶段可以保证窗口中的字符串是没有重复的呢？
这里和之前不一样，要在收缩窗口完成后更新 res，因为窗口收缩的 while 条件是存在重复元素，换句话说收缩完成后一定保证窗口中没有重复嘛。
class Solution {
public int lengthOfLongestSubstring(String s) {
Map<Character,Integer> window = new HashMap<>();
int left = 0, right = 0;
int res = 0;
while(right < s.length()){
char c = s.charAt(right);
right++;
window.put(c,window.getOrDefault(c,0)+1);
while(window.get(c) > 1){
char d = s.charAt(left);
left++;
window.put(d,window.get(d)-1);
}
res = Math.max(res,right - left);//while中不满足条件，所以待窗口调整后再更新res
}
return res;
}
}五、长度最小的子数组
LeetCode209题
class Solution {
public int minSubArrayLen(int target, int[] nums) {
/**
//暴力解法
int result = Integer.MAX_VALUE;
int sum = 0;//子序列的值
int subLength = 0;//子序列的长度
for(int i = 0; i < nums.length; i++){
sum = 0;
for(int j = i; j < nums.length; j++){
sum += nums[j];
if(sum >= target){ //如果子序列的值大与target，则更新result
subLength = j - i + 1;
result = result < subLength ? result : subLength;
break;
}
}
}
return result == Integer.MAX_VALUE ? 0 : result;
*/
int left = 0, right = 0;
int sum = 0;
int result = Integer.MAX_VALUE;
while(right < nums.length){
sum += nums[right];
right++;
while(sum >= target){
result = Math.min(result,right - left); //while中满足条件，所以在窗口更新前立即更新result,与上题更新条件的时候不同
sum -= nums[left];
left++;
}
}
return result == Integer.MAX_VALUE ? 0 : result;
}
}边栏推荐
猜你喜欢
随机推荐
云服务器web项目部署详解
C语言教程 - 制作单位转换器
同时求最大值与最小值（看似简单却值得思考~）
单火线开关设计详解
网站开发方案研究
IDEA2021.2安装与配置（持续更新）
写博客的原因。
LT9211芯片资料分享
[Arduino uses a rotary encoder module]
进程(下):进程控制、终止、等待、替换
向龙芯2K1000板子上烧写中标麒麟系统
Industry where edge gateway strong?
开源代码交叉编译操作流程及遇到的问题解决（lightdm）
2019 - ICCV - 图像修复 Image Inpainting 论文导读《StructureFlow: Image Inpainting via Structure-aware ~~》
USB HUB USB集线器电路设计
Pylon CLI 低成本的本地环境管控工具应用实例
振芯GM7123C：功能RGB转VGA芯片方案简介
VCA821可变增益放大器
基于阿里云OSS+PicGo的个人图床搭建
将ORCAD原理图导入allegro中进行PCB设计