当前位置:首页 » 《资源分享》 » 正文

滑不动窗口的秘密—— “滑动窗口“算法 (Java版)

27 人参与  2024年10月20日 14:00  分类 : 《资源分享》  评论

点击全文阅读


本篇会加入个人的所谓鱼式疯言

❤️❤️❤️鱼式疯言:❤️❤️❤️此疯言非彼疯言
而是理解过并总结出来通俗易懂的大白话,
小编会尽可能的在每个概念后插入鱼式疯言,帮助大家理解的.
???可能说的不是那么严谨.但小编初心是能让更多人能接受我们这个概念 !!!

在这里插入图片描述

前言

学习完了 双指针算法,相比小伙伴应该对我们的 双指针算法 烂熟于心了吧 ? ? ?

接下来迎面走来的就是我们的 == “滑动窗口” 算法== ,什么是滑动窗口算法,该怎么用,有哪些特殊的场景,下面就请宝子们和我一起推开 “滑动窗口” 算法的大门吧 ? ? ?

目录

滑动窗口的初识

滑动窗口的应用

滑动窗口的结论

一. 滑动窗口的初识

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,如果可以翻转最多 k0 ,则返回 数组中连续 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 的嵌套 ,一端固定 ,一端移动,并且通过 满足 个数时候的 子数组的长度

解法二

滑动窗口

还是先 定义两个指针 ,leftright 都指向 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>. 讲解算法思想

当我们分析这题时,肯定少不了要统计 字符串中每个字符出现的 个数 ,这时我们就需要 借用一个工具 来使用

那就是我们的 哈希表? ? ?

本题解法

滑动窗口 + 哈希表

算法步骤

先定义两个哈希表 hash1hash2 分别统计 st 中出现字符的个数 先把 t 中 的每个字符都存入到哈希表 hash1 中

入窗口

在这里插入图片描述

然后再 用 滑动窗口 ,先让 right 一直往右走, 一直进入哈希表 , 当 hash2 【A】 <= hash1 【A】 (其他字符以此类推) , 我们就用count 来统计增加的个数, 否则 count 不变

更新结果

当 count 的值 = 数组长度 时 , 我们就 更新结果,记录当前 下标

出窗口操作

先 去除 hash2left 当前下标的字符

如果我们的 当 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 的个数中, 见识到了如何根据我们需要的条件来 入窗口出窗口
调整滑动窗口的方法来解决我们 一段有单调性并且连续的子数组 或者 子字符串 的问题

而我们又在 “最小覆盖子串” 和 “串联所有单词的子串” 中, 通过 以 滑动窗口哈希表 的思想共同
解决我们的 ***包含该元素却是无序的情况 *** 的一种算法问题 。

如果觉得小编写的还不错的咱可支持 三连 下 (定有回访哦) , 不妥当的咱请评论区 指正

希望我的文章能给各位宝子们带来哪怕一点点的收获就是 小编创作 的最大 动力 ? ? ?

在这里插入图片描述


点击全文阅读


本文链接:http://zhangshiyu.com/post/174555.html

<< 上一篇 下一篇 >>

  • 评论(0)
  • 赞助本站

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

关于我们 | 我要投稿 | 免责申明

Copyright © 2020-2022 ZhangShiYu.com Rights Reserved.豫ICP备2022013469号-1