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

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

❤️❤️❤️鱼式疯言:❤️❤️❤️此疯言非彼疯言

而是理解过并总结出来通俗易懂的大白话,

小编会尽可能的在每个概念后插入鱼式疯言,帮助大家理解的.

可能说的不是那么严谨.但小编初心是能让更多人能接受我们这个概念 ！！！

前言

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

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

目录

1. 滑动窗口的初识

2. 滑动窗口的应用

3. 滑动窗口的结论

一. 滑动窗口的初识

1. 滑动窗口的简介

滑动窗口算法是一种常用的 解决字符串/数组子串问题 的算法。它通过维护一个窗口，该窗口在字符串/数组上滑动，每次滑动一个位置，并根据问题的要求调整窗口的 大小和位置 。

通过不断滑动窗口，可以有效地解决 字符串/数组子串问题 。

滑动窗口算法的基本思想是通过两个指针（左指针和右指针）来定义窗口的边界。

2. 滑动窗口如何使用

初始时，左指针和右指针都指向字符串/数组的 第一个元素 ，然后右指针开始向右移动，直到满足某个 条件（如子串的长度等）时停止。

然后左指针开始向右移动，同时 缩小窗口的大小，直到不满足某个条件时停止。

这样，通过不断地向右移动 右指针 和 左指针，可以在 字符串/数组上 滑动窗口，并根据问题的要求进行相应的 调整和计算。

滑动窗口算法在求解字符串/数组子串问题时具有 高效性 ，因为它将问题的规模由 O(n^2) 降低到O(n) ，而且只需要遍历一次 字符串/数组 。同时，滑动窗口算法也可以解决一些 其他类型的问题，

如求解最长不重复子串、找到满足特定条件的子串等。

鱼式疯言

滑动窗口本质上还是一种 双指针算法 ，

而我们滑动窗口的这个 “窗口” 其实就是双指针所围成的 一段区间

二. 滑动窗口的应用

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

. 讲解算法思想

当我们看到这道题时，我们是需要两个数来充当我们的 左边界 和 右边界 的

解法一:

暴力枚举

我们就可以通过先 固定左边界 的值，来移动右边界 的方式来查找我们需要的最小子数组的长度

解法二 ：

滑动窗口

我们在解法一的基础上优化出 “滑动窗口” 的算法思路

滑动窗口算法的 三步骤 ：

先

用定义两个指针 left 和 right 让我们都指向 零位置

入窗口操作

先让 right 不断向右移动， 并用 sum 来计算滑动窗口内的总和

出窗口操作

当我们 sum 满足 >= target 时， 我们就让 left 也 向右移动，同时 sum 减去 left

位置的值

更新结果

当我们 每次满足 sum >= right 时，就 更新 每次的长度，直到找到 最小 的那个长度为止

. 编写代码

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= target) {                              len= Math.min(len,right-left+1);               sum -= nums[left];                left++;                            }         }         return len > sz ? 0: len;    }}

鱼式疯言

说两点小编自己的体会

1. 在我们的滑动窗口算法中 ， right 不需要回退 的，当我们需要改变 “窗口” 的状态时， 唯一要看的是条件需要什么，来移动我们的 left 的位置来调整

 for( ;right   
终止条件的判定，我们只需要让 right 走完整个数组 即可 ，因为这个 滑动的 “窗口” 存在 于 有实际含义的区域
当 right 出了数组，也就意味着 滑动窗口 就不存在了
  
2. 最大连续1 的个数
 
1004.最大连续 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 个零 的最长子数组
  
. 讲解算法思想
 
题目分析 ：
 
我们需要的是 1 的长度，但是 1 却有可能会加入 0
 
那我们不妨从 正难则反 的思维来统计 零 出现的个数
   
当 零的个数  k 时候，我们就减少零的个数
  
解法一 :
 
暴力枚举
 
还是两个 for 的嵌套 ，一端固定 ，一端移动，并且通过 满足 零 个数时候的 子数组的长度
 
解法二 ：
 
滑动窗口
 
还是先 定义两个指针 ，left，right 都指向 0 下标的位置
 
入窗口操作
   
让 right 一直 向右 移动 ，并用 zero 来统计 出现过的 零 的个数， 只要 零 的个数  k 时，就让 left ++ 向右移动 , 直到 zero     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  
 
鱼式疯言
 
小编这里最想强调的一点就是我们 这个解题的思维
 
这个思路： 正难则反
 
题目要求是统计 1出现的子数组的长度
 
当我们只需要从 反面 来统计 出现 零的个数， 进行 滑动窗口的 出 和 入
 
3. 最小覆盖子串
 
76.最小覆盖子串题目链接
 
. 题目描述
  
给你一个字符串 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 每一个的子串的 下标
 
. 讲解算法思想
 
当我们分析这题时，肯定少不了要统计 字符串中每个字符出现的 个数 ，这时我们就需要 借用一个工具 来使用
 
那就是我们的 哈希表  
 
本题解法：
 
滑动窗口 + 哈希表
 
算法步骤
   
先定义两个哈希表 hash1 和 hash2 分别统计 s 和 t 中出现字符的个数
先把 t 中 的每个字符都存入到哈希表 hash1 中
入窗口
    
然后再 用 滑动窗口 ，先让 right 一直往右走， 一直进入哈希表 ， 当 hash2 【A】     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