【优选算法 — 滑动窗口】滑动窗口小专题(一)

 


长度最小的子数组 

 长度最小的子数组


题目解析:

 

对于示例一

 对于剩下两种示例:

  解法一:暴力枚举  

把所有的子数组全部枚举出来,并且枚举出的每一个子数组求和判断,返回长度最小的子数组;


  时间复杂度 :

枚举子数组 N^2 ,求和 N —> O(N^3)


数组中全都是正整数,所以加的数越多,和就越大,所以这就可以利用单调性来优化

优化暴力枚举,要让时间复杂度从 O(N^3) 优化到 O(N^2)

我们先定义出左区间 left ,然后不着急枚举右区间 right,先定义一个变量 sum ,来统计以 left 为左区间的所有子数组的和:

刚刚的暴力枚举,是先枚举右边,并且每枚举一次,都要判断当前子数组是否是合适的子数组 ;

而优化的方法为,定义一个sum,在 right 向右枚举时,每枚举一个数,都把这个数加到 sum 上

优化后,就可以省去找到子数组后(找到合适的位置,固定 left 和 right ),从前往后遍历,再相加的步骤;

此时我们就找到了一个合适的子数组,长度为4,既然已经找到合适的子数组,并且数组中都是正整数,那么我们就没有必要再让 right 继续往后枚举了,因为要返回的是长度最小的子数组;

此时就需要让 left++,此时,我们不需要着急更新 right,先计算 新left 和当前 right 组成的子数组 sum 是否满足条件;

所以在找到合适的子数组后,处理好后,先要让 sum = sum - nums[left] ,再让 left++即可


解法二:利用单调性,使用 “同向双指针”(“滑动窗口”)


(如果遇到在 right++ 后 依旧是 sum > target ,让 left++,而不是 right--)

如果 sum < target,right++ (进窗口);sum > target,left++(出窗口) 

因为在找合适子数组的过程中,left 和 right 一直是向右移动的,right 在 left++ 之后,是不会回退的,所以叫“同向双指针” ,“同向双指针”,又叫“滑动窗口”;

当我们发现可以利用单调性,使得两个指针都可以不会退(本题因为给的数组元素都是正整数,可以利用单调性,进而运用“滑动窗口”思想)

  1. 先初始化左窗口和右窗口(用 left 和 right 标记左区间和右区间,区间代表窗口)
  2. 进窗口  (right++)
  3. 判断(这个题需要在判断结果的时候更新结果,其他题目可能在进窗口更新结果)
  4. 出窗口  (right++)
  5. 循环进窗口和出窗口的过程  (回退到判断的步骤)

(更新结果的步骤是就题论题的,有的题目是进窗口时更新结果,有的是判断的时候才更新结果) 

滑动窗口能保证正确性,因为通过利用单调性,规避了很多没有意义的枚举行为,一定能在不断更新的过程中,得到一个最终的结果,这个结果就一定是正确的。


  时间复杂度  

哪怕代码是两层 for 循环,但是根据实际情况,我们每一步操作都只会让 left 或者 right 向后移动一格,最坏的情况:

刚开始初始化好指针后,就在判断下执行进窗口的操作(right++),在right = length 后,程序又通过判断执行出窗口操作(left++),这种最坏的情况操作 left 和 right 的次数为 2N;

所以时间复杂度为 O(N)


  编写代码  


  错误代码: 

  正确代码 : 


  无重复字符的最长子串  


解法一:暴力枚举 + 哈希表(判断字符是否重复出现)


  • 暴力枚举,就是以某一个字符为起点,开始向后遍历字符串;
  • 并且把遍历到的每一个字符,都放入  hash 表 中,进行判断当前遍历字符是否重复出现;
  • 如果重复出现,则停止遍历,统计当前子串长度(哈希表中的元素个数),并且让起点向后挪动一位;

  时间复杂度:

分析最坏情况下的时间复杂度,最坏情况下,因为是暴力枚举,从起点开始向后遍历字符串,并且起点从 字符串的第一个元素 到 字符串的最后一个元素 ;这个过程枚举到的所有子串中,返回最大子串长度;

所以时间复杂度是 O(N^2)


我们定义 left 指针指向起点并且固定,right 指针从 left 指针开始遍历;

每次遍历到一个字符,就判断该字符是否出现在哈希表中;

直到来到出现重复字符的位置,并且 right 记录下该字符的位置 ;

如果是暴力枚举,在 right 指向重复字符位置,记录下当前子串长度;

记录下当前子串长度之后,left往后挪动一位,right 重新回到 left 指针的位置;

然后继续重复上述过程;


  方法二:滑动窗口  


当 right 到达重复字符的位置,然后统计当前子串的长度;

然后 left 向后挪,挪动到当前子串中,与 right 所指向的字符相同的字符,所在的位置的后一位;

此时,right 无需再像暴力枚举一样,又回到 left 之前的位置,因为在 left 按照上面的规则,移动好位置后,新的 left 与 right 之间,是没有重复元素的;

此时,继续向后挪动 right 即可;

上述情况,left 和 right 移动的方向相同,所以这种方法就是滑动窗口。

对于上面这种题,对于我们最重要的启发,就是能分析出为什么使用滑动窗口:


要想清楚这题的做法是滑动窗口,要能根据例子,推断出 left 和 right 两个指针不用回退,并且 left 和 right 的移动情况(不一定是只后挪一位)


  编写代码  


对于本题,我们并不需要真的去 new 一个哈希表,可以用数组模拟哈希表;

只需要 new 一个最大容量为 128 的数组即可,因为所有我们常见的字符数为128;

数组的下标表示,每个字符的 ASCLL 码值;

如果该字符出现一次,该字符的 ASCLL码值对应的数组下标元素 +1;


  时空复杂度  


  时间复杂度:


O(N),虽然有两层循环,但是与上一题类似,要根据具体的情况分析时间复杂度;


  空间复杂度:


 ​​

​​

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/912439.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

半波整流器原理

一、二极管不控整流 1.阻性负载 1.1.电路拓扑结构 电路只由交流源、二极管和电阻组成。最基本的带阻性负载的半波整流器如图所示。输入源为交流源&#xff0c;目标是使输出电压含有非零直流分量&#xff0c;负载为R。功率二极管只允许电流往一个方向流动。 1.2.工作模态分析…

yolov8涨点系列之引入CBAM注意力机制

文章目录 YOLOv8 中添加注意力机制 CBAM 具有多方面的好处特征增强与选择通道注意力方面空间注意力方面 提高模型性能计算效率优化&#xff1a; yolov8增加CBAM具体步骤CBAM代码(1)在__init.pyconv.py文件的__all__内添加‘CBAM’(2)conv.py文件复制粘贴CBAM代码(3)修改task.py…

Rust-AOP编程实战

文章本天成&#xff0c;妙手偶得之。粹然无疵瑕&#xff0c;岂复须人为&#xff1f;君看古彝器&#xff0c;巧拙两无施。汉最近先秦&#xff0c;固已殊淳漓。胡部何为者&#xff0c;豪竹杂哀丝。后夔不复作&#xff0c;千载谁与期&#xff1f; ——《文章》宋陆游 【哲理】文章…

基于 SSM(Spring + Spring MVC + MyBatis)框架构建电器网上订购系统

基于 SSM&#xff08;Spring Spring MVC MyBatis&#xff09;框架构建电器网上订购系统可以为用户提供一个方便快捷的购物平台。以下将详细介绍该系统的开发流程&#xff0c;包括需求分析、技术选型、数据库设计、项目结构搭建、主要功能实现以及前端页面设计。 需求分析 …

Docker部署Oracle 11g

1&#xff0c;拉取镜像&#xff1a; sudo docker pull registry.cn-hangzhou.aliyuncs.com/helowin/oracle_11gsudo docker images 2&#xff0c;启动一个临时容器&#xff0c;用于拷贝数据库文件&#xff0c;挂载到宿主主机&#xff0c;使数据持久化&#xff1a; sudo docke…

Linux操作系统:学习进程_了解并掌握进程的状态

对进程状态之间转换感到头疼&#xff0c;只听书本概念根本无法理解&#xff0c;死记硬背不是什么好的解决方法。只有进行底层操作去了解每一个进程状态&#xff0c;才能彻底弄清楚进程状态是如何转换的。 一、进程的各个状态 我们先从Linux内核数据结构来看&#xff1a; 每一个…

分布式环境下宕机的处理方案有哪些?

大家好&#xff0c;我是锋哥。今天分享关于【分布式环境下宕机的处理方案有哪些&#xff1f;】面试题。希望对大家有帮助&#xff1b; 分布式环境下宕机的处理方案有哪些&#xff1f; 1000道 互联网大厂Java工程师 精选面试题-Java资源分享网 在现代分布式系统中&#xff0c;…

接触角测量(Contact Angle Measurement)

接触角是指液滴在固体表面上的形态&#xff0c;特别是在气、液、固三相交界点处&#xff0c;气-液界面切线与固-液交界线之间的夹角。这个角度是衡量液体对固体表面润湿性的一个重要参数。接触角的大小可以反映液体与固体之间的相互作用强度&#xff0c;从而了解液体在固体表面…

《操作系统 - 清华大学》2 -2:中断、异常和系统调用

文章目录 1. 中断和异常处理机制1.1 中断1.2 异常 2. 系统调用2.1 标志C库的例子2.2 编程接口 3.系统调用的实现4. 程序调用和系统调用的不同处5. 中断、异常和系统调用的开销 1. 中断和异常处理机制 接下来看一看中断和异常的处理过程&#xff0c;看下图就比较清楚&#xff0…

Nginx简易配置将内网网站ssh转发到外网

声明&#xff1a;本内容仅供交流学习使用&#xff0c;部署网站上线还需要根据有关规定申请域名以及备案。 背景 在内网的服务器有一个运行的网页&#xff0c;现使用ssh反向代理&#xff0c;将它转发到外网的服务器。 但是外网的访问ip会被ssh反向代理拦截 所以使用Nginx进行…

Moment.js、Day.js、Miment,日期时间库怎么选?

一直以来&#xff0c;处理时间和日期的JavaScript库&#xff0c;选用的都是Momment.js。它的API清晰简单&#xff0c;使用方便灵巧&#xff0c;功能还特别齐全。 大师兄是Moment.js的重度使用者。凡是遇到时间和日期的操作&#xff0c;就把Moment.js引用上。 直到有天我发现加…

后台管理系统窗体程序:文章管理 > 文章发表

目录 文章列表的的功能介绍&#xff1a; 1、进入页面 2、页面内的各种功能设计 &#xff08;1&#xff09;进入选择 &#xff08;2&#xff09;当获取到唯一标识符时 &#xff08;3&#xff09;当没有标识符时 &#xff08;4&#xff09;发布按钮&#xff0c;存为草稿 一、网…

Linux服务控制及系统基本加固

一. liunx操作系统的开机引导的过程 1. 开机自检 根据bios的设置&#xff0c;对cpu,内存&#xff0c;显卡&#xff0c;键盘等等设备进行初步检测如果以上检测设备工作正常&#xff0c;系统会把控制权移交到硬盘 总结:检测出包含系统启动操作系统的设备&#xff0c;硬盘&#…

通过 SSH 隧道将本地端口转发到远程主机

由于服务器防火墙,只开放了22端口,想要通过5901访问服务器上的远程桌面,可以通过下面的方式进行隧道转发。 一、示例命令 这条代码的作用是通过 SSH 创建一个 本地端口转发,将你本地的端口(5901)通过加密的 SSH 隧道连接到远程服务器上的端口(5901)。这种方式通常用于在…

WPF+MVVM案例实战与特效(二十八)- 自定义WPF ComboBox样式:打造个性化下拉菜单

文章目录 1. 引言案例效果3. ComboBox 基础4. 自定义 ComboBox 样式4.1 定义 ComboBox 样式4.2 定义 ComboBoxItem 样式4.3 定义 ToggleButton 样式4.4 定义 Popup 样式5. 示例代码6. 结论1. 引言 在WPF应用程序中,ComboBox控件是一个常用的输入控件,用于从多个选项中选择一…

C#中日期和时间的处理

目录 前言 时间对于我们的作用 一些关于时间的名词说明 格里高利历 格林尼治时间(GMT) 协调世界时(UTC) 时间戳 DateTime 初始化 获取时间 计算时间 字符串转DateTime 存储时间 TimeSpan 初始化它来代表时间间隔 用它相互计算 自带常量方便用于和ticks进行计…

pdb和gdb的双剑合璧,在python中调试c代码

左手编程&#xff0c;右手年华。大家好&#xff0c;我是一点&#xff0c;关注我&#xff0c;带你走入编程的世界。 公众号&#xff1a;一点sir&#xff0c;关注领取python编程资料 问题背景 正常情况下&#xff0c;调试python代码用pdb&#xff0c;调试c代码用gdb&#xff0c;…

【Apache ECharts】<农作物病害发生防治面积>

在vs Code里打开&#xff0c; 实现 1. 首先引入 echarts.min.js 资源 2. 在body部分设一个 div&#xff0c;设置 id 为 main 3. 设置 script 3.1 基于准备好的dom&#xff0c;初始化echarts实例 var myChart echarts.init(document.getElementById(main)); 3.2 指定图表的…

Docker + Jenkins + gitee 实现CICD环境搭建

目录 前言 关于Jenkins 安装Jenkins docker中运行Jenkins注意事项 通过容器中的Jenkins&#xff0c;把服务打包到docker进行部署 启动Jenkins 创建第一个任务 前言 CI/CD&#xff08;持续集成和持续交付/持续部署&#xff09;&#xff0c;它可以实现自动化的构建、测试和部署…

Leetcode 买卖股票的最佳时机 Ⅱ

使用贪心算法来解决此问题&#xff0c;通过在价格上涨的每一天买入并在第二天卖出的方式&#xff0c;累计所有上涨的利润&#xff0c;以实现最大收益。关键点是从第二天开始遍历&#xff0c;并且只要当前比前一天价格高&#xff0c;我们就在前一天买入然后第二天卖出去。下面是…