[Algorithm][滑动窗口][长度最小的子数组] + 滑动窗口原理
目录
- 0.滑动窗口原理讲解
- 1.长度最小的子数组
- 1.题目链接
- 2.算法原理讲解
- 3.代码实现
0.滑动窗口原理讲解
- 滑动窗口:“同向双指针”
- 滑动窗口可处理「⼀段连续的区间」问题
- 如何使用?
left = 0, right = 0
- 进窗口
- 判断
- 是否出窗口
- 更新结果 -> 视情况而定
- 可能在出窗口前
- 可能在进窗口之后
- 具体原理解析将结合**「长度最小的子数组」**来说明
1.长度最小的子数组
1.题目链接
- 长度最小的子数组
2.算法原理讲解
-
此问题分析的对象是**「⼀段连续的区间」,因此可以考虑「滑动窗⼝」**的思想来解决
-
让滑动窗⼝满⾜:
- 从
i
位置开始,窗⼝内所有元素的和⼩于target
- 当窗⼝内元素之和第⼀次⼤于等于⽬标值的时候,就是
i
位置开始满⾜条件的最⼩⻓度
- 从
-
做法:
- 如果窗⼝
sum >= target
:- 更新结果,并且将左端元素划出去的同时继续判断是否满⾜条件并更新结果
- 因为左端元素可能很⼩,划出去之后依旧满⾜条件
- 更新结果,并且将左端元素划出去的同时继续判断是否满⾜条件并更新结果
- 如果窗⼝
sum
不满⾜条件:right++
,让下⼀个元素进⼊窗⼝
- 如果窗⼝
-
为何滑动窗⼝可以解决问题,并且时间复杂度更低?
- 这个窗⼝寻找的是:以当前窗⼝最左侧元素(记为
left1
)为基准,符合条件的情况- 即:从
left1
开始,满⾜sum >= target
时的最右侧(记为right1
)能到哪⾥
- 即:从
- 既然已经找到从
left1
开始的最优的区间,那么就可以⼤胆舍去left1
- 但是如果继续像暴力求解⽅法⼀样,重新开始统计第⼆个元素(
left2
)往后的和,势必会有⼤量重复的计算- 因为在求第⼀段区间的时候,已经算出很多元素的和了,这些和是可以在计算下次区间和的时候⽤上的
- 但是如果继续像暴力求解⽅法⼀样,重新开始统计第⼆个元素(
- 此时,
rigth1
的作⽤就体现出来了,只需将left1
这个值从sum
中剔除- 从
right1
这个元素开始,往后找满⾜left2
元素的区间- 此时
right1
也有可能是满⾜的,因为left1
可能很⼩,sum
剔除掉left1
之后,依旧满⾜⼤于等于 target
- 此时
- 从
- 这样就能省掉⼤量重复的计算
- 总结:利用单调性,规避了很多没有必要的枚举行为
- 此处的单调指滑动窗口内
sum
的单调性,而不是数组原始数据的单调性
- 此处的单调指滑动窗口内
- 这个窗⼝寻找的是:以当前窗⼝最左侧元素(记为
-
时间复杂度: O ( N ) O(N) O(N)
- 虽然代码是两层循环,但是
left
指针和right
指针都是不回退的,两者最多都往后移动n
次
- 虽然代码是两层循环,但是
3.代码实现
int MinSubArrayLen(int target, vector<int>& nums)
{int sum = 0, len = INT_MAX;for(int left = 0, right = 0; right < nums.size(); right++){sum += nums[right]; // 进窗口while(sum >= target) // 判断{len = min(len, right - left + 1); // 更新结果sum -= nums[left++]; // 出窗口}}return len == INT_MAX ? 0 : len;
}
相关文章:
[Algorithm][滑动窗口][长度最小的子数组] + 滑动窗口原理
目录 0.滑动窗口原理讲解1.长度最小的子数组1.题目链接2.算法原理讲解3.代码实现 0.滑动窗口原理讲解 滑动窗口:“同向双指针”滑动窗口可处理「⼀段连续的区间」问题如何使用? left 0, right 0进窗口判断 是否出窗口 更新结果 -> 视情况而定 可能…...
.NET 发布,部署和运行应用程序
.NET应用发布 发布.Net应用有很多种方式,下面列举三种发布方式: 单文件发布跨平台发布Docker发布 单文件发布 右键工程,选择“发布”,部署模式选择“独立”,目标运行时选择自己想要部署到的系统,我这里用…...
B树(B-tree)
B树(B-tree) B树(B-tree)是一种自平衡的多路查找树,主要用于磁盘或其他直接存取的辅助存储设备 B树能够保持数据有序,并允许在对数时间内完成查找、插入及删除等操作 这种数据结构常被应用在数据库和文件系统的实现上 B树的特点包括: B树为…...
EelasticSearch是什么?及EelasticSearch的安装
一、概述 Elasticsearch 是一个基于 Apache Lucene 构建的开源分布式搜索引擎和分析引擎。它专为云计算环境设计,提供了一个分布式的、高可用的实时分析和搜索平台。Elasticsearch 可以处理大量数据,并且具备横向扩展能力,能够通过增加更多的…...
Python机器学习项目开发实战:如何进行语音识别
注意:本文的下载教程,与以下文章的思路有相同点,也有不同点,最终目标只是让读者从多维度去熟练掌握本知识点。 下载教程:Python机器学习项目开发实战_语音识别_编程案例解析实例详解课程教程.pdf 在Python机器学习项目…...
2024年五一杯数学建模C题思路分析
文章目录 1 赛题思路2 比赛日期和时间3 组织机构4 建模常见问题类型4.1 分类问题4.2 优化问题4.3 预测问题4.4 评价问题 5 建模资料 1 赛题思路 (赛题出来以后第一时间在CSDN分享) https://blog.csdn.net/dc_sinor?typeblog 2 比赛日期和时间 报名截止时间:2024…...
【代码】Python3|Requests 库怎么继承 Selenium 的 Headers (2024,Chrome)
本文使用的版本: Chrome 124Python 12Selenium 4.19.0 版本过旧可能会出现问题,但只要别差异太大,就可以看本文,因为本文对新老版本都有讲解。 文章目录 1 难点解析和具体思路2 注意事项2.1 PDF 资源获取时注意事项2.2 Capabiliti…...
JAVA程序设计-对象设计
无论是根据某马还是某谷的适配教程做项目时候,发现了大部分都是重复的crud,大部分只要做好笔记复习即可,但是却往往忘记了编码设计,所以这里开始复习编码设计,对象设计中,长期使用Mp的那一套导致就是Service Mapper,一套梭哈完了,这样很容易忘记基本功夫 POJO: 简单…...
蓝桥杯2024年第十五届省赛真题-R 格式
找到规律后如下,只需要用高精度加法和四舍五入(本质也是高精度加法就能做),如果没有找到规律,就得自己写高精度乘法和加法,不熟练很容易错。 //#include<bits/stdc.h> #include<iostream> #i…...
Linux服务器硬件及RAID配置
一、服务器硬件 塔式服务器:最初的服务器形态之一,类似于传统的台式电脑,但具有更强的处理能力和稳定性,适合小型企业或部门使用。 机架式服务器:设计为可安装在标准化机架内的模块化单元,可以有效地节省空…...
前端 vue单页面中请求数量过多问题 控制单页面请求并发数
需求背景: 页面中需要展示柜子,一个柜子需要调用 详情接口以及状态接口 也就是说有一个柜子就需要调用两个接口,在项目初期,接手的公司项目大概也就4-5个柜子,最多的也不超过10个,但是突然进来一个项目&a…...
HarmonyOS开发实例:【分布式手写板】
介绍 本篇Codelab使用设备管理及分布式键值数据库能力,实现多设备之间手写板应用拉起及同步书写内容的功能。操作流程: 设备连接同一无线网络,安装分布式手写板应用。进入应用,点击允许使用多设备协同,点击主页上查询…...
Unity TMP Inputfield 输入框 框选 富文本 获取真实定位
一、带富文本标签的框选是什么 UGUI的InputField提供了selectionAnchorPosition和selectionFocusPosition,开始选择时的光标下标和当前光标下标 对于未添加富文本标签时,直接通过以上两个值,判断一下框选方向(前向后/后向前&…...
如何在原生项目中集成flutter
两个前提条件: 从flutter v1.17版本开始,flutter module仅支持AndroidX的应用在release模式下flutter仅支持一下架构:x84_64、armeabi-v7a、arm6f4-v8a,不支持mips和x86;所以引入flutter前需要在app/build.gradle下配置flutter支持的架构 a…...
【设计模式】策略模式
目录 什么是策略模式 代码实现 什么是策略模式 策略模式是一种行为型设计模式,它定义了一系列算法,将每个算法封装成一个独立的对象,使得它们可以相互替换。 在策略模式中,通常有三个角色: 环境类(Cont…...
Java面试八股之Iterator和ListIterator的区别是什么
Iterator和ListIterator的区别是什么 这道题也是考查我们对迭代器相关的接口的了解程度,从代码中我们可以看出后者是前者的子接口,在此基础上做了一些增强,并且只用于List集合类型。 定义与基本概念 Iterator: 定义:…...
服务器中毒怎么办?企业数据安全需重视
互联网企业: 广义的互联网企业是指以计算机网络技术为基础,利用网络平台提供服务并因此获得收入的企业。广义的互联网企业可以分为:基础层互联网企业、服务层互联网企业、终端层互联网企业。 狭义的互联网企业是指在互联网上注册域名,建立网…...
k8s使用harbor私有仓库镜像 —— 筑梦之路
官方文档: Secret | Kubernetes ImagePullSecrets的设置是kubernetes机制的另一亮点,习惯于直接使用Docker Pull来拉取公共镜像,但非所有容器镜像都是公开的。此外,并不是所有的镜像仓库都允许匿名拉取,也就是说需要身份认证&…...
tcp bbr pacing 的对与错
前面提到 pacing 替代 burst 是大势所趋,核心原因就是摩尔定律逐渐失效,主机带宽追平交换带宽,交换机不再能轻易吸收掉主机突发,且随着视频类流量激增,又不能以大 buffer 做带宽后备。因此,主机必须 pacing…...
MySQL学习-非事务相关的六大日志、InnoDB的三大特性以及主从复制架构
一. 六大日志 慢查询日志:记录所有执行时间超过long_query_time的查询,方便定位并优化。 # 查询当前慢查询日志状态 SHOW VARIABLES LIKE slow_query_log; #启用慢查询日志 SET GLOBAL slow_query_log ON; #设置慢查询文件位置 SET GLOBAL slow_query_log_file …...
【软件测试】MIL/HIL/PIL/SIL测试
V字型开发流程 引用文章:汽车行业V模型开发详解 V模型开发(V-Model Development)是一种广泛应用于汽车行业的系统开发方法。它以字母“V”形状的图表形式展示了开发过程中不同阶段之间的关系,从需求分析到系统整合和验证&#x…...
WebKit结构深度解析:打造高效与安全的浏览器引擎
WebKit结构深度解析:打造高效与安全的浏览器引擎 在现代网络世界中,浏览器作为连接用户与互联网信息的桥梁,其背后的技术架构至关重要。WebKit,作为当今最流行的开源浏览器引擎之一,其结构设计和功能实现对于提升浏览…...
SQLSERVER对等发布问题处理
问题1: 无法对 数据库Sast_Business 执行 删除,因为它正用于复制。 (.Net SqlClient Data Provider) 处理: USE [master]; GO EXEC sp_replicationdboption dbname NSast_Business, optname Npublish, value Nfalse; EXEC sp_replica…...
CentOS 7 中时间快了 8 小时
1.查看系统时间 1.1 timeZone显示时区 [adminlocalhost ~]$ timedatectlLocal time: Mon 2024-04-15 18:09:19 PDTUniversal time: Tue 2024-04-16 01:09:19 UTCRTC time: Tue 2024-04-16 01:09:19Time zone: America/Los_Angeles (PDT, -0700)NTP enabled: yes NTP synchro…...
itext7 pdf转图片
https://github.com/thombrink/itext7.pdfimage 新建asp.net core8项目,安装itext7和system.drawing.common 引入itext.pdfimage核心代码 imageListener下有一段不安全的代码 unsafe{for (int y 0; y < image.Height; y){byte* ptrMask (byte*)bitsMask.Scan…...
搜维尔科技:Manus Xsens Metagloves新一代手指捕捉
Manus Xsens Metagloves新一代手指捕捉 搜维尔科技:Manus Xsens Metagloves新一代手指捕捉...
Python与Redis:提升性能,确保可靠性,掌握最佳实践
在 Python 中,有多个库可用于与 Redis 数据库进行交互,其中最受欢迎的是 redis-py。这是一个 Python 客户端库,提供了与 Redis 数据库进行通信的丰富功能。 Python操作Redis操作步骤 安装 redis-py 使用 pip 安装 redis-py: p…...
GPT国内能用吗
2022年11月,Open AI发布ChatGPT,ChatGPT展现了大型语模型在自然语言处理方面的惊人进步,其生成文本的流畅度和连贯性令人印象深刻,为AI应用打开了新的可能性。 ChatGPT的出现推动了AI技术在各个领域的应用,例如&#x…...
中科亿海微-CL1656功能验证开发板
I. 引言 A. 研究背景与意义 CL1656是一款精度高、功耗低、成本低的5V单片低功耗运放,由核心互联公司研发制造,CL1656 是一个 16-bit、快速、低功耗逐次逼近型 ADC,吞吐速率高达 250 kSPS,并且内置低噪声、宽 带宽采样保持放大器。…...
学习STM32第十五天
SPI外设 一、简介 STM32F4XX内部集成硬件SPI收发电路,可以由硬件自动执行时钟生成、数据收发等功能,减轻CPU负担,可配置8位/16位数据帧,高位(最常用)/低位先行,三组SPI接口,支持DMA…...
dede资讯类网站模板/上海网络营销公司
近年来游戏行业火爆起来的往往是能让玩家快速入手的小游戏和便捷手游,众多游戏产品中,微信小程序上的游戏属于热门云游戏的领域吗?作为能在手机上玩端游的云游戏,微信上的小游戏和云游戏有什么本质上的区别吗?两者的定…...
微信后台怎么做微网站/东莞网站建设平台
前言 相信不少小伙伴对开源项目 httprunner 都很感兴趣,我们来看下它的有哪些特点吧: 项目管理:新增项目、列表展示及相关操作,支持用例批量上传(标准化的HttpRunner json和yaml用例脚本)模块管理:为项目新增模块&…...
动易网站建设/google网站
1.变量和类型写代码时,变量是存放数据的载体。在计算机内存中,变量是物理存储器中的一块内存空间,因此变量可以被读取和修改。数据的种类繁多,变量的种类也与之对应。文本,数值,图像,音频&#…...
做网站哪里的好/网站可以自己做吗
我正在为一个Python编码类写一个项目,我有一个问题。我正在编写一个Reversi引擎,它将在一个游戏中查看几步前进,然后选择它认为最好的移动。虽然我知道python不是一种理想的语言(因为它没有其他语言那么快),但我认为可以编写至少具…...
品牌网站建设要选磐石网络/附近的成人电脑培训班
项目框架中有一个函数,其中一步是判断传入的参数值和数据库中的某个值是否相等。原本数据库的值规定为varchar类型,该函数没有任何问题。现在有个需求是需要把数据库中的整数或长整数类型的值读入之后再做判断,参数传入之后判断相等总返回fal…...
律师个人网站建设/今天的新闻内容
2019独角兽企业重金招聘Python工程师标准>>> 目录 引言写在前面一App IDbundle identifier二设备Device三开发证书Certificates 证书的概念数字证书的概念iOS开发证书iOS开发证书的根证书申请证书CSRCertificate Signing Request四供应配置文件Provisioning Profil…...