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

「优选算法刷题」:长度最小的子数组

一、题目

给定一个含有 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

二、思路解析

这道题也是一道很经典的 “滑动窗口” 例题,需要利用单调性,使用 “同向双指针” 来对暴力解法 「会超时」进行优化,以让时间复杂度达到要求。

但是,为何使用滑动窗口呢?

回到我们的分析对象,是「⼀段连续的区间」,我就是根据这个条件去判别的。

让滑动窗⼝满⾜:从 i 位置开始,窗⼝内所有元素的和⼩于  target (那么当窗⼝内元素之和
第⼀次⼤于等于⽬标值的时候,就是  i  位置开始,满⾜条件的最⼩⻓度)。

具体做法是,将右端元素划⼊窗⼝中,统计出此时窗⼝内元素的和:

▪ 如果窗⼝内元素之和⼤于等于? target :更新结果,并且将左端元素划出去的同时继续判
断是否满⾜条件并更新结果(因为左端元素可能很⼩,划出去之后依旧满⾜条件)
▪ 如果窗⼝内元素之和不满⾜条件: right++ ,另下⼀个元素进⼊窗⼝。

最后返回最短的数值即可。

三、完整代码

class Solution {public int minSubArrayLen(int target, int[] nums) {int len = Integer.MAX_VALUE;int n = nums.length;int sum = 0;for(int left = 0,right = 0;right < n;right++){sum  += nums[right];// 进窗⼝// 判断while(sum >= target){// 更新结果len = Math.min(len,right-left+1);// 出窗⼝sum -= nums[left++];}}return len == Integer.MAX_VALUE?0:len;}
}

以上就是本篇博客的全部内容啦,如有不足之处,还请各位指出,期待能和各位一起进步!

相关文章:

「优选算法刷题」:长度最小的子数组

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

RuoYi-Cloud本地部署--详细教程

文章目录 1、gitee项目地址2、RuoYi-Cloud架构3、本地部署3.1 下载项目3.2 idea打开项目3.3 启动nacos3.4 若依数据库准备3.5 启动redis3.6 修改nacos中的各个模块的配置文件3.7 启动ruoyi前端项目3.8 启动各个微服务模块 4、启动成功 1、gitee项目地址 https://gitee.com/y_p…...

如何优雅的发布一个 TypeScript 软件包?

向 NPM 发布软件包本身并不是一个特别困难的挑战。但是&#xff0c;配置你的 TypeScript 项目以取得成功可能是一个挑战。你的软件包能在大多数项目上运行吗&#xff1f;用户能否使用类型提示和自动完成功能&#xff1f;它能与 ES Modules (ESM) 和 CommonJS (CJS) 风格的导入一…...

总结的太到位:python 多线程系列详解

前言&#xff1a; 上vip课的时候每次讲到框架的执行&#xff0c;就会有好学的同学问用多线程怎么执行&#xff0c;然后我每次都会说在测开课程会详细讲解&#xff0c;这并不是套路&#xff0c;因为如果你不理解多线程&#xff0c;不清楚什么时候该用什么时候不该用&#xff0c;…...

惬意上手Python —— 装饰器和内置函数

1. Python装饰器 Python中的装饰器是一种特殊类型的函数&#xff0c;它允许用户在不修改原函数代码的情况下&#xff0c;增加或修改函数的行为。 具体来说,装饰器的工作原理基于Python的函数也是对象这一事实&#xff0c;可以被赋值给变量、作为参数传递给其他函数或者作为其他…...

python 调用dll

在Python中&#xff0c;可以使用ctypes库来调用DLL文件。ctypes库是一个标准库&#xff0c;用于在Python中加载共享库&#xff08;例如DLL文件&#xff09;并调用其中的函数。 以下是一个简单的示例&#xff0c;演示如何使用ctypes库调用DLL文件中的函数&#xff1a; import c…...

docker里Java服务执行ping命令模拟流式输出

文章目录 业务场景处理解决实现ping功能并实时返回输出实现长ping和中断请求docker容器找不到ping命令处理 业务场景 我们某市的客户&#xff0c;一直使用CS版本的信控平台&#xff0c;直接安装客户Windows server服务器上&#xff0c;主要对信号机设备进行在线管理、方案配时…...

代码随想录算法训练营第十三天| 239. 滑动窗口最大值 、347.前 K 个高频元素

239. 滑动窗口最大值 思路&#xff1a; 用遍历区间的元素时&#xff0c;维护一个单调队列&#xff0c;从大到小排列。 要找到最大值&#xff0c;实际单调队列保存区间内最大值及最大值右侧的第二大值&#xff08;用于当前最大值处于区间左端&#xff0c;在区间右移时更新临时最…...

旋转花键的使用寿命与机械原理分析

旋转花键是一种传动部件&#xff0c;广泛应用于各种机械设备中。对于厂商来说&#xff0c;如何保证使用寿命是重中之重&#xff0c;而旋转花键的使用寿命与其机械原理密切相关&#xff0c;了解其机械原理有助于更好地维护和使用旋转花键&#xff0c;从而提高其使用寿命。 旋转花…...

互联网摸鱼日报(2024-01-22)

互联网摸鱼日报(2024-01-22) 开源中国资讯 Stability AI 推出更小、更高效的 1.6B 语言模型 X 正面向 Android 推出音频和视频通话 Extism —— WebAssembly 插件实现框架 Gitee 推荐 | 龙蜥社区最佳安全加固实践指南 security-benchmark 每日一博 | 得物云原生容器技术探…...

CentOS 7 安装配置MySQL

目录 一、安装MySQL​编辑​编辑 1、检查MySQL是否安装及版本信息​编辑 2、卸载 2.1 rpm格式安装的mysql卸载方式 2.2 二进制包格式安装的mysql卸载 3、安装 二、配置MySQL 1、修改MySQL临时密码 2、允许远程访问 2.1 修改MySQL允许任何人连接 2.2 防火墙的问题 2…...

Gold-YOLO(NeurIPS 2023)论文与代码解析

paper&#xff1a;Gold-YOLO: Efficient Object Detector via Gather-and-Distribute Mechanism official implementation&#xff1a;https://github.com/huawei-noah/Efficient-Computing/tree/master/Detection/Gold-YOLO 存在的问题 在过去几年里&#xff0c;YOLO系列已经…...

多个coco数据标注文件合并

一、coco数据集是什么&#xff1f; COCO&#xff08;Common Objects in Context&#xff09;是一个用于目标检测和图像分割任务的标注格式。如果你有多个COCO格式的JSON文件&#xff0c;你可能需要将它们合并成一个文件&#xff0c;以便更方便地处理和管理数据。在这篇博客中&…...

Kubernetes(K8S)拉取本地镜像部署Pod 实现类似函数/微服务功能(可设置参数并实时调用)

以两数相加求和为例&#xff0c;在kubernetes集群拉取本地的镜像&#xff0c;实现如下效果&#xff1a; 1.实现两数相加求和 2.可以通过curl实时调用&#xff0c;参数以GET方式提供&#xff0c;并得到结果。&#xff08;类似调用函数&#xff09; 一、实现思路 需要准备如下的…...

k8s使用ingress实现应用的灰度发布升级

v1是1.14.0版本nginx ,实操时候升级到v2是1.20.0版本nginx&#xff0c;来测试灰度发布实现过程 一、方案&#xff1a;使用ingress实现应用的灰度发布 1、服务端&#xff1a;正常版本v1&#xff0c;灰度升级版本v2 2、客户端&#xff1a;带有请求头versionv2标识的请求访问版…...

最新热门商用GPT4.0带MJ绘画去授权版本自定义三方接口(开心版)

一台VPS 搭建宝塔 解析域名 上传程序至根目录 访问首页在线安装配置数据库 PHP版本选择:7.3 安装完成后访问网站首页即可&#xff01; 配置APIKEY&#xff0c;登录网站后台自定义配置&#xff0c;不然网站无法使用&#xff01; 网站后台地址/admin 默认账号:admin 密码…...

Halcon基于形状的模板匹配inspect_shape_model

Halcon基于形状的模板匹配 基于形状的匹配&#xff0c;就是使用目标对象的轮廓形状来描述模板。Halcon中有操作助手&#xff0c;可以直观 地进行形状模板匹配的参数选择以及效果测试。如果使用算子编写&#xff0c;步骤如下。 &#xff08;1&#xff09;从参考图像上选择检测的…...

html中根元素以及根元素字体的含义

在 HTML 中&#xff0c;根元素是指 <html> 标签&#xff0c;可以使用 CSS 来设置根元素的字体大小。根元素的字体大小会影响整个页面的文本内容&#xff0c;默认情况下&#xff0c;根元素的字体大小是浏览器默认的大小。 要设置根元素的字体大小&#xff0c;你可以使用 …...

51单片机1-6

目录 单片机介绍 点亮一个LED 流水灯参考代码 点亮流水LEDplus版本 独立按键 独立按键控制LED亮灭 静态数码管 静态数码管显示 动态数码管显示 模块化编程 调试工具 矩阵键盘 矩阵键盘显示数据 矩阵键盘密码锁 学习B站江协科技课程笔记。 安装keil&#xff0c;下…...

vue2(Vuex)、vue3(Pinia)、react(Redux)状态管理

vue2状态管理Vuex Vuex 是一个专为 Vue.js应用程序开发的状态管理模式。它使用集中式存储管理应用的所有组件的状态&#xff0c;以及规则保证状态只能按照规定的方式进行修改。 State&#xff08;状态&#xff09;:Vuex 使用单一状态树&#xff0c;即一个对象包含全部的应用层…...

Docker 离线安装指南

参考文章 1、确认操作系统类型及内核版本 Docker依赖于Linux内核的一些特性&#xff0c;不同版本的Docker对内核版本有不同要求。例如&#xff0c;Docker 17.06及之后的版本通常需要Linux内核3.10及以上版本&#xff0c;Docker17.09及更高版本对应Linux内核4.9.x及更高版本。…...

python打卡day49

知识点回顾&#xff1a; 通道注意力模块复习空间注意力模块CBAM的定义 作业&#xff1a;尝试对今天的模型检查参数数目&#xff0c;并用tensorboard查看训练过程 import torch import torch.nn as nn# 定义通道注意力 class ChannelAttention(nn.Module):def __init__(self,…...

.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 适用场…...

【网络安全产品大调研系列】2. 体验漏洞扫描

前言 2023 年漏洞扫描服务市场规模预计为 3.06&#xff08;十亿美元&#xff09;。漏洞扫描服务市场行业预计将从 2024 年的 3.48&#xff08;十亿美元&#xff09;增长到 2032 年的 9.54&#xff08;十亿美元&#xff09;。预测期内漏洞扫描服务市场 CAGR&#xff08;增长率&…...

聊聊 Pulsar:Producer 源码解析

一、前言 Apache Pulsar 是一个企业级的开源分布式消息传递平台&#xff0c;以其高性能、可扩展性和存储计算分离架构在消息队列和流处理领域独树一帜。在 Pulsar 的核心架构中&#xff0c;Producer&#xff08;生产者&#xff09; 是连接客户端应用与消息队列的第一步。生产者…...

大语言模型如何处理长文本?常用文本分割技术详解

为什么需要文本分割? 引言:为什么需要文本分割?一、基础文本分割方法1. 按段落分割(Paragraph Splitting)2. 按句子分割(Sentence Splitting)二、高级文本分割策略3. 重叠分割(Sliding Window)4. 递归分割(Recursive Splitting)三、生产级工具推荐5. 使用LangChain的…...

微信小程序 - 手机震动

一、界面 <button type"primary" bindtap"shortVibrate">短震动</button> <button type"primary" bindtap"longVibrate">长震动</button> 二、js逻辑代码 注&#xff1a;文档 https://developers.weixin.qq…...

Qwen3-Embedding-0.6B深度解析:多语言语义检索的轻量级利器

第一章 引言&#xff1a;语义表示的新时代挑战与Qwen3的破局之路 1.1 文本嵌入的核心价值与技术演进 在人工智能领域&#xff0c;文本嵌入技术如同连接自然语言与机器理解的“神经突触”——它将人类语言转化为计算机可计算的语义向量&#xff0c;支撑着搜索引擎、推荐系统、…...

多模态大语言模型arxiv论文略读(108)

CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文标题&#xff1a;CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文作者&#xff1a;Sayna Ebrahimi, Sercan O. Arik, Tejas Nama, Tomas Pfister ➡️ 研究机构: Google Cloud AI Re…...

2025季度云服务器排行榜

在全球云服务器市场&#xff0c;各厂商的排名和地位并非一成不变&#xff0c;而是由其独特的优势、战略布局和市场适应性共同决定的。以下是根据2025年市场趋势&#xff0c;对主要云服务器厂商在排行榜中占据重要位置的原因和优势进行深度分析&#xff1a; 一、全球“三巨头”…...