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

邂逅岁月

已于 2024-05-23 13:09:25 修改

阅读量4.9k

点赞数 105

分类专栏：题海寻offer “掌掴”算法之路数据结构的九曲回肠文章标签：算法面试求职招聘刷题创业创新

于 2024-05-23 13:04:23 首次发布

本文链接：https://blog.csdn.net/mgzdwm/article/details/138958430

版权

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

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

在这里插入图片描述

前言

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

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

一. 滑动窗口的初识

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;
    }
}