滑不动窗口的秘密—— “滑动窗口“算法 (Java版)
本篇会加入个人的所谓鱼式疯言
❤️❤️❤️鱼式疯言:❤️❤️❤️此疯言非彼疯言
而是理解过并总结出来通俗易懂的大白话,
小编会尽可能的在每个概念后插入鱼式疯言,帮助大家理解的.
🤭🤭🤭可能说的不是那么严谨.但小编初心是能让更多人能接受我们这个概念 ！！！
前言
学习完了 双指针算法，相比小伙伴应该对我们的 双指针算法 烂熟于心了吧 💖 💖 💖
接下来迎面走来的就是我们的 == “滑动窗口” 算法== ,什么是滑动窗口算法，该怎么用，有哪些特殊的场景，下面就请宝子们和我一起推开 “滑动窗口” 算法的大门吧 💞 💞 💞
目录
-
滑动窗口的初识
-
滑动窗口的应用
-
滑动窗口的结论
一. 滑动窗口的初识
1. 滑动窗口的简介
滑动窗口算法是一种常用的 解决字符串/数组子串问题 的算法。它通过维护一个窗口，该窗口在字符串/数组上滑动，每次滑动一个位置，并根据问题的要求调整窗口的 大小和位置 。
通过不断滑动窗口，可以有效地解决 字符串/数组子串问题 。
滑动窗口算法的基本思想是通过两个指针（左指针和右指针）来定义窗口的边界。
2. 滑动窗口如何使用
初始时，左指针和右指针都指向字符串/数组的 第一个元素 ，然后右指针开始向右移动，直到满足某个 条件（如子串的长度等）时停止。
然后左指针开始向右移动，同时 缩小窗口的大小，直到不满足某个条件时停止。
这样，通过不断地向右移动 右指针 和 左指针，可以在 字符串/数组上 滑动窗口，并根据问题的要求进行相应的 调整和计算。
滑动窗口算法在求解字符串/数组子串问题时具有 高效性 ，因为它将问题的规模由 O(n^2) 降低到O(n) ，而且只需要遍历一次 字符串/数组 。同时，滑动窗口算法也可以解决一些 其他类型的问题，
如求解最长不重复子串、找到满足特定条件的子串等。
鱼式疯言
滑动窗口本质上还是一种 双指针算法 ，
而我们滑动窗口的这个 “窗口” 其实就是双指针所围成的 一段区间
二. 滑动窗口的应用
1. 长度最小的子数组
长度最小的子数组题目链接
<1>. 题目描述
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, …,
numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
示例 1：
输入： target = 7, nums = [2,3,1,2,4,3]
输出： 2
解释：
子数组 [4,3] 是该条件下的长度最小的子数组。
示例 2：
输入： target = 4, nums = [1,4,4]
输出： 1
示例 3：
输入： target = 11, nums = [1,1,1,1,1,1,1,1]
输出： 0
题目含义:
找到一群 最短 连续的元素，这群元素之和大于等于 我们的目标值 target
<2>. 讲解算法思想
当我们看到这道题时，我们是需要两个数来充当我们的 左边界 和 右边界 的
解法一:
暴力枚举
我们就可以通过先 固定左边界 的值，来移动右边界 的方式来查找我们需要的最小子数组的长度
解法二 ：
滑动窗口
我们在解法一的基础上优化出 “滑动窗口” 的算法思路
滑动窗口算法的 三步骤 ：
先
用定义两个指针 left 和 right 让我们都指向
零位置
入窗口操作
先让 right 不断向右移动， 并用 sum 来计算滑动窗口内的总和
出窗口操作
当我们
sum满足>= target时， 我们就让left也 向右移动，同时sum减去left
位置的值
更新结果
当我们 每次满足 sum >= right 时，就 更新 每次的长度，直到找到 最小 的那个长度为止
<3>. 编写代码
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int sz=nums.length;
int left=0,right=0;
int sum=0,len=Integer.MAX_VALUE;
for( ;right< sz;right++) {
sum += nums[right];
while(sum >= target) {
len= Math.min(len,right-left+1);
sum -= nums[left];
left++;
}
}
return len > sz ? 0: len;
}
}
鱼式疯言
说两点小编自己的体会
- 在我们的滑动窗口算法中 ，
right不需要回退 的，当我们需要改变 “窗口” 的状态时， 唯一要看的是条件需要什么，来移动我们的left的位置来调整
for( ;right< sz;right++) { }
- 终止条件的判定，我们只需要让
right走完整个数组 即可 ，因为这个 滑动的 “窗口” 存在 于 有实际含义的区域当 right 出了数组，也就意味着
滑动窗口就不存在了
2. 最大连续1 的个数
1004.最大连续 1 的个数 题目链接
<1>. 题目描述
给定一个二进制数组 nums 和一个整数 k，如果可以翻转最多 k 个 0 ，则返回 数组中连续 1 的最大个数 。
示例 1：
输入：nums = [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，最长的子数组长度为 6。
示例 2：
输入：nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3
输出：10
解释：[0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
粗体数字从 0 翻转到 1，最长的子数组长度为 10。
题目含义:
寻找一段连续有
1的数组，如果存在零的话，并可以补最多 k 个零 的最长子数组
<2>. 讲解算法思想
题目分析 ：
我们需要的是 1 的长度，但是 1 却有可能会加入 0
那我们不妨从 正难则反 的思维来统计 零 出现的个数
当
零的个数 <= k的时候就统计长度， 当> k时候，我们就减少零的个数
解法一 :
暴力枚举
还是两个 for 的嵌套 ，一端固定 ，一端移动，并且通过 满足 零 个数时候的 子数组的长度
解法二 ：
滑动窗口
还是先 定义两个指针 ，left，right 都指向 0 下标的位置
入窗口操作
让
right一直 向右 移动 ，并用zero来统计 出现过的零 的个数， 只要零的个数<= k
我们就一直入窗口
出窗口
当 zero 的个数 > k 时，就让 left ++ 向右移动 , 直到 zero <= k 时，停止 出窗口
更新结果
只要
零 的个数 <= k, 我们就不断更新结果，直到找到我们 最长的子数组
<3>. 编写代码
class Solution {
public int longestOnes(int[] nums, int k) {
int sz= nums.length;
if(k >= sz) return sz;
int sum=0,zero=0;
int ret=0;
for(int left=0, right=0; right < sz ;right++) {
// 统计 0 的个数来进窗口
if(nums[right] == 0) {
zero++;
}
// 通过 0 的个数和 k的大小比较 来出窗口
while(zero > k) {
if(nums[left]==0) {
zero--;
}
left++;
}
ret=Math.max(right-left+1,ret);
}
return ret;
}
}
鱼式疯言
小编这里最想强调的一点就是我们 这个解题的思维
这个思路： 正难则反
题目要求是统计 1出现的子数组的长度
当我们只需要从 反面 来统计 出现 零的个数， 进行 滑动窗口的 出 和 入
3. 最小覆盖子串
76.最小覆盖子串题目链接
<1>. 题目描述
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “” 。
注意：
对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
如果 s 中存在这样的子串，我们保证它是唯一的答案。
示例 1：
输入：s = “ADOBECODEBANC”, t = “ABC”
输出：“BANC”
解释：最小覆盖子串 “BANC” 包含来自字符串 t 的 ‘A’、‘B’ 和 ‘C’。
示例 2：
输入：s = “a”, t = “a”
输出：“a”
解释：整个字符串 s 是最小覆盖子串。
示例 3:
输入: s = “a”, t = “aa”
输出: “”
解释: t 中两个字符 ‘a’ 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。
** 题目含义**
给定一个字符串 s，得到所有包含 t 每一个的子串的 下标
<2>. 讲解算法思想
当我们分析这题时，肯定少不了要统计 字符串中每个字符出现的 个数 ，这时我们就需要 借用一个工具 来使用
那就是我们的 哈希表💞 💞 💞
本题解法：
滑动窗口 + 哈希表
算法步骤
- 先定义两个哈希表
hash1和hash2分别统计s和t中出现字符的个数
- 先把 t 中 的每个字符都存入到哈希表 hash1 中
入窗口
- 然后再 用 滑动窗口 ，先让
right一直往右走， 一直进入哈希表 ， 当 hash2 【A】 <= hash1 【A】 (其他字符以此类推) ， 我们就用count来统计增加的个数， 否则count不变
更新结果
当 count 的值 = 数组长度 时 ， 我们就 更新结果，记录当前
下标
出窗口操作
先 去除 hash2 中 left 当前下标的字符
如果我们的 当 hash2 【A】 <= hash1 【A】 (其他字符以此类推) ， 我们就用count 来 减少成立的个数， 否则 count 不变
<3>. 编写代码
class Solution {
public String minWindow(String s, String t) {
// 先得到两个字符串的长度
int slength=s.length();
int tlength=t.length();
// 先定义两个数组来哈希映射 统计次数
int [] hash1= new int[100];
int [] hash2= new int[100];
// 先统计 s 中 字符的个数
for(int i=0; i < tlength ; ++i) {
hash1[t.charAt(i)-'A']++;
}
int len = Integer.MAX_VALUE;
int begin=Integer.MAX_VALUE;
// 进行滑动窗口操作
for(int left=0,right=0, count=0; right < slength ; right++) {
// 入窗口
char in= s.charAt(right);
hash2[in-'A']++;
// 判断
if(hash2[in-'A'] <= hash1[in-'A']) {
count++;
}
// 更新结果
while(count == tlength) {
// 得到最小长度 并记录起始位置
if(right-left+1 < len) {
begin=left;
len=right-left+1;
}
char out= s.charAt(left);
// 出窗口
if(hash2[out-'A'] <= hash1[out-'A']) {
count--;
}
hash2[out-'A']--;
left++;
}
}
// 不存在直接返回空字符串
if(begin==Integer.MAX_VALUE) return "";
// 截断时要注意 左闭右开
// 当起始位置加上 字符串长度时
// 不需要 -1
return s.substring(begin,begin+len);
}
}
鱼式疯言
对于本题,小编这里有 三点体会 和小伙伴们一起分享
- 当我们需要对滑动窗口进行
出窗口还是入窗口判断时， 用count来统计是否成立的 字符的个数 这个思想是很巧妙的
- 当我们需要统计一个字符串中出现 所有字符的情况 的时候，
哈希表是不错的工具
- 在这里,.我们看到了更新结果的位置是在 入窗口 和出窗口 之间, 上题中我们的更新结果是在 出窗口之后, 所以我们的更新结果是
不固定有可能在 入窗口和出窗口之间 , 也有可能在 == 出窗口 之后==
4. 串联所有单词的子串
30.串联所以单词的子串题目链接
<1>. 题目描述
给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。
s 中的 串联子串 是指一个包含 words 中所有字符串以任意顺序排列连接起来的子串。
例如，如果 words = [“ab”,“cd”,“ef”]， 那么 “abcdef”， “abefcd”，“cdabef”， “cdefab”，“efabcd”，
和 “efcdab” 都是串联子串。 “acdbef” 不是串联子串，因为他不是任何 words 排列的连接。
返回所有串联子串在 s 中的开始索引。你可以以 任意顺序 返回答案。
示例 1：
输入：s = “barfoothefoobarman”, words = [“foo”,“bar”]
输出：[0,9]
解释：因为 words.length == 2 同时 words[i].length == 3，连接的子字符串的长度必须为 6。
子串 “barfoo” 开始位置是 0。它是 words 中以 [“bar”,“foo”] 顺序排列的连接。
子串 “foobar” 开始位置是 9。它是 words 中以 [“foo”,“bar”] 顺序排列的连接。
输出顺序无关紧要。返回 [9,0] 也是可以的。
示例 2：
输入：s = “wordgoodgoodgoodbestword”, words = [“word”,“good”,“best”,“word”]
输出：[]
解释：因为 words.length == 4 并且 words[i].length == 4，所以串联子串的长度必须为 16。
s 中没有子串长度为 16 并且等于 words 的任何顺序排列的连接。
所以我们返回一个空数组。
示例 3：
输入：s = “barfoofoobarthefoobarman”, words = [“bar”,“foo”,“the”]
输出：[6,9,12]
解释：因为 words.length == 3 并且 words[i].length == 3，所以串联子串的长度必须为 9。
子串 “foobarthe” 开始位置是 6。它是 words 中以 [“foo”,“bar”,“the”] 顺序排列的连接。
子串 “barthefoo” 开始位置是 9。它是 words 中以 [“bar”,“the”,“foo”] 顺序排列的连接。
子串 “thefoobar” 开始位置是 12。它是 words 中以 [“the”,“foo”,“bar”] 顺序排列的连接。
题目含义 :
找到所有完全包含
words的字符子串（不包含 每个单词 的顺序，一定是包含单词内每个字符的顺序）
<2>. 讲解算法思想
题目分析:
本题目的是找到相同的 子字符串 ， 而且是不按照顺序的 ，所以我们 还得借用我们的 哈希表 这个工具来完成本题
算法步骤
首先得到 还是定义 一个 left 和 right 来进行 滑动窗口的 操作， 并且定义 两个哈希表
hash1 和 hash2来分别统计 words 和 s 的字符串 出现的次数。
入窗口
我们先让
right吗，以每个 单词的长度 为单位进行移动 ， 截取该 单词长度的子字符串 进入哈希表
- 用 滑动窗口 ，先让
right一直往右走， 一直进入哈希表 ， 当 hash2 【foo】 <= hash1 【foo】 (其他字符以此类推) ， 我们就用count来统计增加的个数， 否则count不变
更新结果
一旦
count满足 字符串数组中所有字符 的总和长度
我们就 更新结果 ,存放该
left的下标
出窗口操作
当 count 满足 字符串数组 长度
更新完结果后， 我们就让 left 也跟着 每个单词(子字符串) 想右移动进行 出窗口 的操作
最后让重新初始化我们的 left 继续每次向右 移动 一格， 只需要 循环移动 每个 子字符串的长度 即可
<3>. 编写代码
class Solution {
public List<Integer> findSubstring(String s, String[] words) {
// 得到每个 字符串以及字符串数组的长度
int slen=s.length();
int wdslen=words.length;
int wlen= words[0].length();
// 定义一个返回结果
List<Integer> ret= new ArrayList<>();
// 先 定义两个 hashMap
// 用于统计 字符串 的数量
Map<String, Integer> hash1= new HashMap<>();
// 统计 words 里面 的长度
for(int i=0; i< wdslen ; i++) {
String str= words[i];
hash1.put(str,hash1.getOrDefault(str,0)+1);
}
// 开始进行滑动窗口操作
for(int j=0; j < wlen ; ++j) {
Map<String, Integer> hash2= new HashMap<>();
// 初始化 left 和 right 的最初位置
int left=j;
int right= j + wlen;
int count=0;
// 设置 right 每次跳跃的 跨度
for( ;right <= slen ; right += wlen) {
// 通过入窗口操作
String in = s.substring(right-wlen,right);
hash2.put(in,hash2.getOrDefault(in,0)+1);
// 判断有效结果
if(hash1.containsKey(in) && hash2.get(in).compareTo(hash1.get(in)) <= 0) {
count++;
}
// 判断是否存在
while(count >= wdslen) {
// 更新结果
if(right-left == wdslen * wlen) {
ret.add(left);
}
String out= s.substring(left,left+wlen);
// 出窗口操作
if(hash1.containsKey(out) && hash2.get(out).compareTo(hash1.get(out)) <= 0) {
count--;
}
// 更新每次 left 跳跃的值
hash2.put(out,hash2.get(out)-1);
left += wlen;
}
}
}
return ret;
}
}
鱼式疯言
以上的整体的思路小编就介绍的差不多，但还有细节问题需要处理
// 通过入窗口操作
String in = s.substring(right-wlen,right);
- 注意这个字符串截取的方法 是
左闭右开区间，就意味着右边的 下标位置是取不到的
// 出窗口操作
if(hash1.containsKey(out) && hash2.get(out).compareTo(hash1.get(out)) <= 0) {
count--;
}
- 首先要包含这个字符串，其次就是当我们 比较两个字符串大小 的时候，不能用
==来比较，只能用compareTo（）来比较两个字符串的大小关系
// 更新结果
if(right-left == wdslen * wlen) {
ret.add(left);
}
- 更新结果的时候，我们获取的是
全部单词长度的总和， 所以 是和 wdslen * wlen 进行比较大小的
三. 滑动窗口的结论
通过文章的学习
- 在滑动窗口的初识 中
我们先是认识到 滑动窗口 本质上就是 两个 指针所围成的区域
而我们通过这个调整这个 区域 来 解决算法问题的方式就是叫 滑动窗口算法
- 在 滑动窗口的应用 中
我们在 长度最小数组 和 最大连续1 的个数中, 见识到了如何根据我们需要的条件来
入窗口和出窗口
调整滑动窗口的方法来解决我们 一段有单调性并且连续的子数组 或者 子字符串 的问题
而我们又在 “最小覆盖子串” 和 “串联所有单词的子串” 中， 通过 以 滑动窗口 和 哈希表 的思想共同
解决我们的 ***包含该元素却是无序的情况 *** 的一种算法问题 。
如果觉得小编写的还不错的咱可支持 三连 下 (定有回访哦) , 不妥当的咱请评论区 指正
希望我的文章能给各位宝子们带来哪怕一点点的收获就是 小编创作 的最大 动力 💖 💖 💖
