当前位置: 首页 > 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;即一个对象包含全部的应用层…...

7.4.分块查找

一.分块查找的算法思想&#xff1a; 1.实例&#xff1a; 以上述图片的顺序表为例&#xff0c; 该顺序表的数据元素从整体来看是乱序的&#xff0c;但如果把这些数据元素分成一块一块的小区间&#xff0c; 第一个区间[0,1]索引上的数据元素都是小于等于10的&#xff0c; 第二…...

利用ngx_stream_return_module构建简易 TCP/UDP 响应网关

一、模块概述 ngx_stream_return_module 提供了一个极简的指令&#xff1a; return <value>;在收到客户端连接后&#xff0c;立即将 <value> 写回并关闭连接。<value> 支持内嵌文本和内置变量&#xff08;如 $time_iso8601、$remote_addr 等&#xff09;&a…...

【Linux】C语言执行shell指令

在C语言中执行Shell指令 在C语言中&#xff0c;有几种方法可以执行Shell指令&#xff1a; 1. 使用system()函数 这是最简单的方法&#xff0c;包含在stdlib.h头文件中&#xff1a; #include <stdlib.h>int main() {system("ls -l"); // 执行ls -l命令retu…...

ssc377d修改flash分区大小

1、flash的分区默认分配16M、 / # df -h Filesystem Size Used Available Use% Mounted on /dev/root 1.9M 1.9M 0 100% / /dev/mtdblock4 3.0M...

MMaDA: Multimodal Large Diffusion Language Models

CODE &#xff1a; https://github.com/Gen-Verse/MMaDA Abstract 我们介绍了一种新型的多模态扩散基础模型MMaDA&#xff0c;它被设计用于在文本推理、多模态理解和文本到图像生成等不同领域实现卓越的性能。该方法的特点是三个关键创新:(i) MMaDA采用统一的扩散架构&#xf…...

微信小程序云开发平台MySQL的连接方式

注&#xff1a;微信小程序云开发平台指的是腾讯云开发 先给结论&#xff1a;微信小程序云开发平台的MySQL&#xff0c;无法通过获取数据库连接信息的方式进行连接&#xff0c;连接只能通过云开发的SDK连接&#xff0c;具体要参考官方文档&#xff1a; 为什么&#xff1f; 因为…...

【学习笔记】深入理解Java虚拟机学习笔记——第4章 虚拟机性能监控,故障处理工具

第2章 虚拟机性能监控&#xff0c;故障处理工具 4.1 概述 略 4.2 基础故障处理工具 4.2.1 jps:虚拟机进程状况工具 命令&#xff1a;jps [options] [hostid] 功能&#xff1a;本地虚拟机进程显示进程ID&#xff08;与ps相同&#xff09;&#xff0c;可同时显示主类&#x…...

Springboot社区养老保险系统小程序

一、前言 随着我国经济迅速发展&#xff0c;人们对手机的需求越来越大&#xff0c;各种手机软件也都在被广泛应用&#xff0c;但是对于手机进行数据信息管理&#xff0c;对于手机的各种软件也是备受用户的喜爱&#xff0c;社区养老保险系统小程序被用户普遍使用&#xff0c;为方…...

安全突围:重塑内生安全体系:齐向东在2025年BCS大会的演讲

文章目录 前言第一部分&#xff1a;体系力量是突围之钥第一重困境是体系思想落地不畅。第二重困境是大小体系融合瓶颈。第三重困境是“小体系”运营梗阻。 第二部分&#xff1a;体系矛盾是突围之障一是数据孤岛的障碍。二是投入不足的障碍。三是新旧兼容难的障碍。 第三部分&am…...

20个超级好用的 CSS 动画库

分享 20 个最佳 CSS 动画库。 它们中的大多数将生成纯 CSS 代码&#xff0c;而不需要任何外部库。 1.Animate.css 一个开箱即用型的跨浏览器动画库&#xff0c;可供你在项目中使用。 2.Magic Animations CSS3 一组简单的动画&#xff0c;可以包含在你的网页或应用项目中。 3.An…...