「算法」滑动窗口

这篇具有很好参考价值的文章主要介绍了「算法」滑动窗口。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

前言

算法需要多刷题积累经验,所以我行文重心在于分析解题思路,理论知识部分会相对简略一些

正文

滑动窗口属于双指针,这两个指针是同向前行,它们所夹的区间就称为“窗口”

啥时候用滑动窗口?

  • 题目涉及到“子序列”、“子数组”、“子串”等概念,要你求和它们相关的量,比如求满足条件的子数组的最大长度
  • 在暴力枚举的时候,如果发现两个“指针”都是朝同一个方向走的,就可以考虑滑动窗口
    注:滑动窗口可以看作是暴力枚举优化后的结果

如何使用?(步骤)

  1. 定义两个“指针”left、right(此“指针”不是真正的指针)
  2. 通过移动 right 让元素进窗口
  3. 进窗口之后进行判断,并根据这个判断决定什么时候需要出窗口

2和3需要放在一个循环里面,这样才可以让窗口不断往前走

  • 在移动“窗口”的过程我们需要不断更新结果,比如求子数组最大长度maxLen,那么每次求出一个子数组长度之后,我们就要判断是否需要更新maxLen
  • 至于是在进窗口后更新结果,还是在出窗口后更新,这就需要结合具体题目分析

例题

长度最小的子数组

思路

  1. 先用暴力枚举看看怎么做,我们先固定一个端点left,然后让right一直往右走,直到[left,right]区间中的元素和大于target,此时得到区间长度为right-left+1
  2. 既然已经比target大,那接下来就别让right往右走了,先让它停下来,因为数组中全是正数,此时right继续走的话,区间中元素总和肯定还是比target大,但是此时区间的长度肯定不是最小长度,这样就做了无用功
  3. 所以我们应该让left向前走,缩小区间,将新区间的元素和与 target 比较,若大于 target,则记录此时区间长度,并让 left 继续向前走;反之则让 right 往前走

「算法」滑动窗口,算法详解,算法,数据结构,java

上面的思路其实就是从暴力枚举逐步过渡到滑动窗口,整个过程下来,我们不难发现:砍掉暴力枚举中那些无用功,也就得到滑动窗口的思路了

代码如下:

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int left = 0,right = 0;  //区间为左闭右闭
        int sum = 0;  //区间中元素总和
        int minLen = nums.length+1;  //最小窗口的长度,一开始初始化为一个比较大的数,不然下面使用取小函数可能没法正确更新minLen
        for(;right < nums.length;right++) {
            sum += nums[right];
            while(sum >= target) {
                minLen = Math.min(minLen,right-left+1);  //更新 minLen
                sum -= nums[left];
                left++;
            }
        }
        
    	return minLen == nums.length+1 ? 0 : minLen;
    }
}

注意:用取小函数来更新 minLen,可以简化代码(相比于使用条件语句判断大小),同理,可以用取大函数来更新最大值

复杂度分析

时间复杂度:O(N),最坏情况下左右指针都要走完整个数组
比如数组大小为5,前四个元素都为1,最后一个为10000,target为10
空间复杂度:O(1)文章来源地址https://www.toymoban.com/news/detail-829587.html

到了这里,关于「算法」滑动窗口的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构-图搜索算法详解

    图搜索算法是数据结构和算法学科中的一个重要领域,它们用于在图中搜索顶点(节点)和边(连接节点的线)。图可以是有向的(边有方向)或无向的(边没有方向)。图搜索算法主要用于解决如路径查找、网络流分析等问题。下面详细介绍几种常见的图搜索算法。 深度优

    2024年04月28日
    浏览(34)
  • 数据结构KMP算法详解

    目录 1. KMP算法是什么? 2. KMP算法的由来 2.1 需要要解决的问题 2.2 一开始想到的方法 2.3 KMP算法诞生了 3.KMP算法的详解 4.KMP算法的实现 5.KMP算法的改进 KMP算法是一种改进的字符串匹配算法,即可以 快速的从主串中找到子串的算法 ,由D.E.Knuth,J.H.Morris和V.R.Pratt提出的,因此人

    2024年02月12日
    浏览(59)
  • [数据结构] 串与KMP算法详解

    今天是农历大年初三,祝大家新年快乐! 尽管新旧交替只是一个瞬间,在大家互祝新年快乐的瞬间,在时钟倒计时数到零的瞬间,在烟花在黑色幕布绽放的瞬间,在心底默默许下愿望的瞬间……跨入新的一年,并不意味了一切都会朝着更美好,也没有什么会从天而降,我们赋

    2024年02月19日
    浏览(41)
  • Offer必备算法_滑动窗口_八道力扣OJ题详解(由浅到深)

    目录 滑动窗口算法介绍 ①力扣209. 长度最小的子数组 解析及代码 ②力扣3. 无重复字符的最长子串 解析及代码 ③力扣1004. 最大连续1的个数 III 解析及代码 ④力扣1658. 将x减到0的最小操作数 解析及代码 ⑤力扣904. 水果成篮 解析及代码1(使用容器) 解析及代码2(开数组) ⑥

    2024年02月20日
    浏览(47)
  • 【数据结构与算法】查找(Search)【详解】

    【知识框架】 查找(Searching) :就是根据给定的某个值,在查找表中确定一个其等于给定值的数据元素( 或记录)。 查找表(Search Table) :是由同一类型的数据元素(或记录)构成的集合。 (Key):数据元素中唯一标识该元素的某个数据项的值,使用基于的查找,查

    2024年02月02日
    浏览(49)
  • 【算法与数据结构】队列的实现详解

    队列的概念: 队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出FIFO(First In First Out) 新添加的元素添加到队尾,只能从队头取出元素。 入队列:进行插入操作的一端称为队尾 出队列:进行删除操作的一端称为队头 队列特征如

    2024年04月13日
    浏览(41)
  • 算法与数据结构 第六章 图(详解)

    目录 一、判断题 二、选择题  在开始之前,先为大家推荐四篇介绍该章四个主要算法的的文章,供大家参考。 Dijkstra算法求最短路径:Dijkstra算法原理_平凡的L同学的博客-CSDN博客_dijiesitela Floyd算法求最短路径:Floyd算法求最短路径 Prim算法求最小生成树:Prim算法求最小生成树

    2024年02月09日
    浏览(47)
  • 【算法与数据结构】栈的实现详解

    栈的概念: 栈 :一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端 称为栈顶,另一端称为栈底。栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则。 压栈:栈的插入操作叫做进栈/压栈/入栈,入数据在栈顶。 出栈:

    2024年03月11日
    浏览(54)
  • 【数据结构与算法】图(Graph)【详解】

    【知识框架】 在线性表中,数据元素之间是被串起来的,仅有线性关系,每个数据元素只有一个直接前驱和一个直接后继。在树形结构中,数据元素之间有着明显的层次关系,并且每一层上的数据元素可能和下一层中多个元素相关,但只能和上一层中一个元素相关。图是一种

    2024年02月02日
    浏览(45)
  • 数据结构与算法之《二叉树》详解

    文章目录 一、树的概念及结构 二、二叉树的概念及结构 2、1 二叉树的概念 2、2 二叉树的特点 2、3 二叉树的结构(图片) 2、4 特殊的二叉树 三、二叉树的代码及思路实现 3、1 二叉树的存储结构 3、1、1 二叉树的顺序存储结构 3、1、2 二叉树的链式存储结构 3、2 二叉树链式

    2024年02月01日
    浏览(45)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包