「优选算法刷题」:长度最小的子数组
一、题目
给定一个含有 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] ,并返回其长度。如果不存在符合条件的子数组,返回 0 。 示例 1: 输…...
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 发布软件包本身并不是一个特别困难的挑战。但是,配置你的 TypeScript 项目以取得成功可能是一个挑战。你的软件包能在大多数项目上运行吗?用户能否使用类型提示和自动完成功能?它能与 ES Modules (ESM) 和 CommonJS (CJS) 风格的导入一…...
总结的太到位:python 多线程系列详解
前言: 上vip课的时候每次讲到框架的执行,就会有好学的同学问用多线程怎么执行,然后我每次都会说在测开课程会详细讲解,这并不是套路,因为如果你不理解多线程,不清楚什么时候该用什么时候不该用,…...
惬意上手Python —— 装饰器和内置函数
1. Python装饰器 Python中的装饰器是一种特殊类型的函数,它允许用户在不修改原函数代码的情况下,增加或修改函数的行为。 具体来说,装饰器的工作原理基于Python的函数也是对象这一事实,可以被赋值给变量、作为参数传递给其他函数或者作为其他…...
python 调用dll
在Python中,可以使用ctypes库来调用DLL文件。ctypes库是一个标准库,用于在Python中加载共享库(例如DLL文件)并调用其中的函数。 以下是一个简单的示例,演示如何使用ctypes库调用DLL文件中的函数: import c…...
docker里Java服务执行ping命令模拟流式输出
文章目录 业务场景处理解决实现ping功能并实时返回输出实现长ping和中断请求docker容器找不到ping命令处理 业务场景 我们某市的客户,一直使用CS版本的信控平台,直接安装客户Windows server服务器上,主要对信号机设备进行在线管理、方案配时…...
代码随想录算法训练营第十三天| 239. 滑动窗口最大值 、347.前 K 个高频元素
239. 滑动窗口最大值 思路: 用遍历区间的元素时,维护一个单调队列,从大到小排列。 要找到最大值,实际单调队列保存区间内最大值及最大值右侧的第二大值(用于当前最大值处于区间左端,在区间右移时更新临时最…...
旋转花键的使用寿命与机械原理分析
旋转花键是一种传动部件,广泛应用于各种机械设备中。对于厂商来说,如何保证使用寿命是重中之重,而旋转花键的使用寿命与其机械原理密切相关,了解其机械原理有助于更好地维护和使用旋转花键,从而提高其使用寿命。 旋转花…...
互联网摸鱼日报(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:Gold-YOLO: Efficient Object Detector via Gather-and-Distribute Mechanism official implementation:https://github.com/huawei-noah/Efficient-Computing/tree/master/Detection/Gold-YOLO 存在的问题 在过去几年里,YOLO系列已经…...
多个coco数据标注文件合并
一、coco数据集是什么? COCO(Common Objects in Context)是一个用于目标检测和图像分割任务的标注格式。如果你有多个COCO格式的JSON文件,你可能需要将它们合并成一个文件,以便更方便地处理和管理数据。在这篇博客中&…...
Kubernetes(K8S)拉取本地镜像部署Pod 实现类似函数/微服务功能(可设置参数并实时调用)
以两数相加求和为例,在kubernetes集群拉取本地的镜像,实现如下效果: 1.实现两数相加求和 2.可以通过curl实时调用,参数以GET方式提供,并得到结果。(类似调用函数) 一、实现思路 需要准备如下的…...
k8s使用ingress实现应用的灰度发布升级
v1是1.14.0版本nginx ,实操时候升级到v2是1.20.0版本nginx,来测试灰度发布实现过程 一、方案:使用ingress实现应用的灰度发布 1、服务端:正常版本v1,灰度升级版本v2 2、客户端:带有请求头versionv2标识的请求访问版…...
最新热门商用GPT4.0带MJ绘画去授权版本自定义三方接口(开心版)
一台VPS 搭建宝塔 解析域名 上传程序至根目录 访问首页在线安装配置数据库 PHP版本选择:7.3 安装完成后访问网站首页即可! 配置APIKEY,登录网站后台自定义配置,不然网站无法使用! 网站后台地址/admin 默认账号:admin 密码…...
Halcon基于形状的模板匹配inspect_shape_model
Halcon基于形状的模板匹配 基于形状的匹配,就是使用目标对象的轮廓形状来描述模板。Halcon中有操作助手,可以直观 地进行形状模板匹配的参数选择以及效果测试。如果使用算子编写,步骤如下。 (1)从参考图像上选择检测的…...
html中根元素以及根元素字体的含义
在 HTML 中,根元素是指 <html> 标签,可以使用 CSS 来设置根元素的字体大小。根元素的字体大小会影响整个页面的文本内容,默认情况下,根元素的字体大小是浏览器默认的大小。 要设置根元素的字体大小,你可以使用 …...
51单片机1-6
目录 单片机介绍 点亮一个LED 流水灯参考代码 点亮流水LEDplus版本 独立按键 独立按键控制LED亮灭 静态数码管 静态数码管显示 动态数码管显示 模块化编程 调试工具 矩阵键盘 矩阵键盘显示数据 矩阵键盘密码锁 学习B站江协科技课程笔记。 安装keil,下…...
vue2(Vuex)、vue3(Pinia)、react(Redux)状态管理
vue2状态管理Vuex Vuex 是一个专为 Vue.js应用程序开发的状态管理模式。它使用集中式存储管理应用的所有组件的状态,以及规则保证状态只能按照规定的方式进行修改。 State(状态):Vuex 使用单一状态树,即一个对象包含全部的应用层…...
PPT|230页| 制造集团企业供应链端到端的数字化解决方案:从需求到结算的全链路业务闭环构建
制造业采购供应链管理是企业运营的核心环节,供应链协同管理在供应链上下游企业之间建立紧密的合作关系,通过信息共享、资源整合、业务协同等方式,实现供应链的全面管理和优化,提高供应链的效率和透明度,降低供应链的成…...
关于nvm与node.js
1 安装nvm 安装过程中手动修改 nvm的安装路径, 以及修改 通过nvm安装node后正在使用的node的存放目录【这句话可能难以理解,但接着往下看你就了然了】 2 修改nvm中settings.txt文件配置 nvm安装成功后,通常在该文件中会出现以下配置&…...
ESP32读取DHT11温湿度数据
芯片:ESP32 环境:Arduino 一、安装DHT11传感器库 红框的库,别安装错了 二、代码 注意,DATA口要连接在D15上 #include "DHT.h" // 包含DHT库#define DHTPIN 15 // 定义DHT11数据引脚连接到ESP32的GPIO15 #define D…...
土地利用/土地覆盖遥感解译与基于CLUE模型未来变化情景预测;从基础到高级,涵盖ArcGIS数据处理、ENVI遥感解译与CLUE模型情景模拟等
🔍 土地利用/土地覆盖数据是生态、环境和气象等诸多领域模型的关键输入参数。通过遥感影像解译技术,可以精准获取历史或当前任何一个区域的土地利用/土地覆盖情况。这些数据不仅能够用于评估区域生态环境的变化趋势,还能有效评价重大生态工程…...
Unit 1 深度强化学习简介
Deep RL Course ——Unit 1 Introduction 从理论和实践层面深入学习深度强化学习。学会使用知名的深度强化学习库,例如 Stable Baselines3、RL Baselines3 Zoo、Sample Factory 和 CleanRL。在独特的环境中训练智能体,比如 SnowballFight、Huggy the Do…...
今日学习:Spring线程池|并发修改异常|链路丢失|登录续期|VIP过期策略|数值类缓存
文章目录 优雅版线程池ThreadPoolTaskExecutor和ThreadPoolTaskExecutor的装饰器并发修改异常并发修改异常简介实现机制设计原因及意义 使用线程池造成的链路丢失问题线程池导致的链路丢失问题发生原因 常见解决方法更好的解决方法设计精妙之处 登录续期登录续期常见实现方式特…...
Mobile ALOHA全身模仿学习
一、题目 Mobile ALOHA:通过低成本全身远程操作学习双手移动操作 传统模仿学习(Imitation Learning)缺点:聚焦与桌面操作,缺乏通用任务所需的移动性和灵活性 本论文优点:(1)在ALOHA…...
VM虚拟机网络配置(ubuntu24桥接模式):配置静态IP
编辑-虚拟网络编辑器-更改设置 选择桥接模式,然后找到相应的网卡(可以查看自己本机的网络连接) windows连接的网络点击查看属性 编辑虚拟机设置更改网络配置,选择刚才配置的桥接模式 静态ip设置: 我用的ubuntu24桌…...
HTML前端开发:JavaScript 获取元素方法详解
作为前端开发者,高效获取 DOM 元素是必备技能。以下是 JS 中核心的获取元素方法,分为两大系列: 一、getElementBy... 系列 传统方法,直接通过 DOM 接口访问,返回动态集合(元素变化会实时更新)。…...
Python竞赛环境搭建全攻略
Python环境搭建竞赛技术文章大纲 竞赛背景与意义 竞赛的目的与价值Python在竞赛中的应用场景环境搭建对竞赛效率的影响 竞赛环境需求分析 常见竞赛类型(算法、数据分析、机器学习等)不同竞赛对Python版本及库的要求硬件与操作系统的兼容性问题 Pyth…...
