当前位置: 首页 > news >正文

LeetCode209. 长度最小的子数组

题目:LeetCode209. 长度最小的子数组

描述:
给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ,并返回其长度。如果不存在符合条件的子数组,返回 0 。

在这里插入图片描述
思路:
滑动窗口
接下来就开始介绍数组操作中另一个重要的方法:滑动窗口。

所谓滑动窗口,就是不断的调节子序列的起始位置和终止位置,从而得出我们要想的结果。

在暴力解法中,是一个for循环滑动窗口的起始位置,一个for循环为滑动窗口的终止位置,用两个for循环 完成了一个不断搜索区间的过程。

那么滑动窗口如何用一个for循环来完成这个操作呢。

首先要思考 如果用一个for循环,那么应该表示 滑动窗口的起始位置,还是终止位置。

如果只用一个for循环来表示 滑动窗口的起始位置,那么如何遍历剩下的终止位置?

此时难免再次陷入 暴力解法的怪圈。

所以 只用一个for循环,那么这个循环的索引,一定是表示 滑动窗口的终止位置。

在本题中实现滑动窗口,主要确定如下三点:

窗口内是什么?
如何移动窗口的起始位置?
如何移动窗口的结束位置?
窗口就是 满足其和 ≥ s 的长度最小的 连续 子数组。

窗口的起始位置如何移动:如果当前窗口的值大于s了,窗口就要向前移动了(也就是该缩小了)。

窗口的结束位置如何移动:窗口的结束位置就是遍历数组的指针,也就是for循环里的索引。

解题的关键在于 窗口的起始位置如何移动,如图所示:
在这里插入图片描述
可以发现滑动窗口的精妙之处在于根据当前子序列和大小的情况,不断调节子序列的起始位置。从而将O(n^2)暴力解法降为O(n)。

public class Solution {public int minSubArrayLen(int target, int[] nums) {int i=0;int sum=0;int length=Integer.MAX_VALUE;for (int j = 0; j < nums.length; j++) {sum+=nums[j];while(sum>=target){length=(j-i+1)<length?(j-i+1):length;sum-=nums[i++];}}return length=length==Integer.MAX_VALUE?0:length;}
}

相关文章:

LeetCode209. 长度最小的子数组

题目&#xff1a;LeetCode209. 长度最小的子数组 描述&#xff1a; 给定一个含有 n 个正整数的数组和一个正整数 target 。 找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl1, …, numsr-1, numsr] &#xff0c;并返回其长度。如果不存在符合条件的子…...

css冒号对齐

实现后的样式效果 实现方式 html&#xff1a; <el-col v-if"item.showInSingle ! false" :span"6" style"padding: 4px 0"><label>{{ item.label }}&#xff1a;</label><span v-if"singleData[item.prop] ! 0 &…...

那些年的golang开发经验记录

goland 问题CreateProcess error216, 该版本的 %1 与你运行的 Windows 版本不兼容。请查看计算机的系统信息&#xff0c;然后联系软件发布者 Cannot run program "......" (in directory "D:\project\go\awesomeProject\src\test"): CreateProcess error2…...

element中select下拉框如何实现宽度自适应

简单暴力&#xff1a; element 和 elementPlus 都可以直接在el-select上添加 style"width: 100%" 解决 <el-select style"width: 100%" v-model"cats" multiple filterable placeholder"请选择分类"> . . . </el-select&…...

springboot项目get请求下划线转驼峰@JsonProperty注解失效问题

问题&#xff1a;解决sprigboot项目get请求中有下划线的入参参数&#xff0c;如&#xff1a;first_name&#xff0c;希望在项目中将下划线格式转成firstName&#xff0c;用JsonProperty注解发现失效问题 1.核查&#xff1a;JsonProperty注解对应包是否正确 正确包&#xff1a…...

架构训练营学习笔记:6-2 微服务基础选型

基础选型 微服务基础设施架构 优先级 其中&#xff0c;核心 就是服务注册、服务发现、服务路由。 模式1-嵌入SDK 模式2-反向代理式 模式3-网络代理式&#xff08;Service Mesh&#xff09; 模式对比 常见微服务框架选择 嵌入SDK-dubbo Spring Cloud 反向代理式 APISIX …...

opencv实战项目 实现手势跟踪并返回位置信息(封装调用)

OpenCV 是一个基于 Apache2.0 许可&#xff08;开源&#xff09;发行的跨平台计算机视觉和机器学习软件库&#xff0c;可以运行在Linux、Windows、Android和Mac OS操作系统上。 需要提前准备opencv 和 mediapipe库 pip --default-timeout5000 install -i https://pypi.tuna.tsi…...

ElementUI动态添加表单项

昨天感冒发烧了&#xff0c;脑子不好使。在实现这个动态表单项时一直报错脑瓜子嗡嗡的&#xff01; 不过好在昨天休息好了&#xff0c;今天起来趁脑瓜子好使&#xff0c;一会就弄好了。 这里记录一下 <el-form-itemv-for"(classId,index) in addFom.classIds":lab…...

Myatis和MybatisPlus常见分页方式

Myatis和MybatisPlus常见分页方式 一、mybaits 原生limit分页 SELECT * FROM order_info limit #{pageNow},#{pageSize}分页插件&#xff08;ssm中&#xff0c;通过xml配置分页。springboot通过则通过配置文件&#xff09; PageHelper插件&#xff1a;PageHelper.startPage(…...

利用ChatGPT绘制思维导图——以新能源汽车竞品分析报告为例

随着人们对环境保护的日益关注和传统燃油汽车的限制&#xff0c;全球范围内对新能源汽车的需求不断增长。新能源汽车市场的激烈竞争使得了解各个竞品的特点和优劣成为关键。然而&#xff0c;针对这一领域的详尽竞品分析却常常需要大量时间和精力。 在此背景下&#xff0c;人工智…...

redis集群搭建(非常详细,适合新手)

免密登录脚本 #!/bin/bash # 检查是否已经存在 SSH 密钥对&#xff0c;如果没有则创建一个 if [ ! -f ~/.ssh/id_rsa ]; thenssh-keygen -t rsa -b 4096 -f ~/.ssh/id_rsa -N fi# 为每个目标主机复制公钥 for ip in 192.168.9.{11..16}; dossh-copy-id -i ~/.ssh/id_rsa.pub …...

CTFshow web93-104关

这周要学习的是php代码审计 根据师兄的作业 来做web入门的93-104关 93关 看代码 进行分析 他的主函数 include("flag.php"); highlight_file(__FILE__); if(isset($_GET[num])){ $num $_GET[num]; if($num4476){ die("no no no!"); …...

ElasticSearch详细操作

ElasticSearch搜索引擎详细操作以及概念 文章目录 ElasticSearch搜索引擎详细操作以及概念 1、_cat节点操作1.1、GET/_cat/nodes&#xff1a;查看所有节点1.2、GET/_cat/health&#xff1a;查看es健康状况1.3_、_GET/_cat/master&#xff1a;查看主节点1.4、GET/_cat/indices&a…...

【OpenVINOSharp】 基于C#和OpenVINO2023.0部署Yolov8全系列模型

基于C#和OpenVINO2023.0部署Yolov8全系列模型 1 项目简介1.1 OpenVINOTM 2 OpenVinoSharp2.1 OpenVINOTM 2023.0安装配置2.2 C 动态链接库2.3 C#构建Core推理类2.4 NuGet安装OpenVinoSharp 3 获取和转换Yolov8模型3.1 安装ultralytics3.2 导出yolov8模型3.3 安装OpenVINOTM Pyt…...

121. 买卖股票的最佳时机

题目描述 给定一个数组 prices &#xff0c;它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。 你只能选择 某一天 买入这只股票&#xff0c;并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。 返回你可以从这笔交易中获取的…...

FDO(Feedback-Driven Optimization) LTO(Link-Time Optimization)

反馈驱动优化&#xff08;Feedback-Driven Optimization&#xff0c;FDO&#xff09;和链接时优化&#xff08;Link-Time Optimization&#xff0c;LTO&#xff09;是两种重要的编译器优化技术。下面我们详细介绍这两种技术&#xff1a; 反馈驱动优化 (FDO)&#xff1a; FDO 是…...

低成本无刷高速吹风机单片机方案

高速吹风机的转速一般是普通吹风机的5倍左右。一般来说&#xff0c;吹风机的电机转速一般为2-3万转/分钟&#xff0c;而高速吹风机的电机转速一般为10万转/分钟左右。高转速增加了高风速。一般来说&#xff0c;吹风机的风力只有12-17米/秒&#xff0c;而高速吹风机的风力可以达…...

使用Python爬取某查查APP端(Appium自动化篇)

1. 写在前面 某查查网站反爬虫风控还是较强的&#xff0c;之后会分别介绍一下PC端协议、APP端自动化、APP端接口协议三种采集方案。这里主要介绍APP端的自动化方式&#xff0c;APP端自动化方式需要登陆账号&#xff0c;协议的话需要签名授权&#xff08;自动化经测试没有太多限…...

vue3实现组件可拖拽 vuedraggable

npm i -S vuedraggablenext 中文文档&#xff0c;里面有完整代码案例&#xff0c;值得一看 vue.draggable vue3 版本在工作台中的应用场景 - itxst.com...

gradio常用组件

gradio常用组件 1.gradio程序启动2.写入html相关代码3.文本框4. 回车触发事件5.选择按钮框6.下拉框7.点击按钮8.清空按钮9.监听组件10.输出流11.template 1.gradio程序启动 import gradio as gr def tab():pass with gr.Blocks() as ui:gr.Markdown("# <center>&am…...

国防科技大学计算机基础课程笔记02信息编码

1.机内码和国标码 国标码就是我们非常熟悉的这个GB2312,但是因为都是16进制&#xff0c;因此这个了16进制的数据既可以翻译成为这个机器码&#xff0c;也可以翻译成为这个国标码&#xff0c;所以这个时候很容易会出现这个歧义的情况&#xff1b; 因此&#xff0c;我们的这个国…...

在软件开发中正确使用MySQL日期时间类型的深度解析

在日常软件开发场景中&#xff0c;时间信息的存储是底层且核心的需求。从金融交易的精确记账时间、用户操作的行为日志&#xff0c;到供应链系统的物流节点时间戳&#xff0c;时间数据的准确性直接决定业务逻辑的可靠性。MySQL作为主流关系型数据库&#xff0c;其日期时间类型的…...

.Net框架,除了EF还有很多很多......

文章目录 1. 引言2. Dapper2.1 概述与设计原理2.2 核心功能与代码示例基本查询多映射查询存储过程调用 2.3 性能优化原理2.4 适用场景 3. NHibernate3.1 概述与架构设计3.2 映射配置示例Fluent映射XML映射 3.3 查询示例HQL查询Criteria APILINQ提供程序 3.4 高级特性3.5 适用场…...

《Playwright:微软的自动化测试工具详解》

Playwright 简介:声明内容来自网络&#xff0c;将内容拼接整理出来的文档 Playwright 是微软开发的自动化测试工具&#xff0c;支持 Chrome、Firefox、Safari 等主流浏览器&#xff0c;提供多语言 API&#xff08;Python、JavaScript、Java、.NET&#xff09;。它的特点包括&a…...

【AI学习】三、AI算法中的向量

在人工智能&#xff08;AI&#xff09;算法中&#xff0c;向量&#xff08;Vector&#xff09;是一种将现实世界中的数据&#xff08;如图像、文本、音频等&#xff09;转化为计算机可处理的数值型特征表示的工具。它是连接人类认知&#xff08;如语义、视觉特征&#xff09;与…...

Linux-07 ubuntu 的 chrome 启动不了

文章目录 问题原因解决步骤一、卸载旧版chrome二、重新安装chorme三、启动不了&#xff0c;报错如下四、启动不了&#xff0c;解决如下 总结 问题原因 在应用中可以看到chrome&#xff0c;但是打不开(说明&#xff1a;原来的ubuntu系统出问题了&#xff0c;这个是备用的硬盘&a…...

C++ 求圆面积的程序(Program to find area of a circle)

给定半径r&#xff0c;求圆的面积。圆的面积应精确到小数点后5位。 例子&#xff1a; 输入&#xff1a;r 5 输出&#xff1a;78.53982 解释&#xff1a;由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982&#xff0c;因为我们只保留小数点后 5 位数字。 输…...

Map相关知识

数据结构 二叉树 二叉树&#xff0c;顾名思义&#xff0c;每个节点最多有两个“叉”&#xff0c;也就是两个子节点&#xff0c;分别是左子 节点和右子节点。不过&#xff0c;二叉树并不要求每个节点都有两个子节点&#xff0c;有的节点只 有左子节点&#xff0c;有的节点只有…...

虚拟电厂发展三大趋势:市场化、技术主导、车网互联

市场化&#xff1a;从政策驱动到多元盈利 政策全面赋能 2025年4月&#xff0c;国家发改委、能源局发布《关于加快推进虚拟电厂发展的指导意见》&#xff0c;首次明确虚拟电厂为“独立市场主体”&#xff0c;提出硬性目标&#xff1a;2027年全国调节能力≥2000万千瓦&#xff0…...

Chrome 浏览器前端与客户端双向通信实战

Chrome 前端&#xff08;即页面 JS / Web UI&#xff09;与客户端&#xff08;C 后端&#xff09;的交互机制&#xff0c;是 Chromium 架构中非常核心的一环。下面我将按常见场景&#xff0c;从通道、流程、技术栈几个角度做一套完整的分析&#xff0c;特别适合你这种在分析和改…...