「优选算法刷题」:长度最小的子数组
一、题目
给定一个含有 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 使用单一状态树,即一个对象包含全部的应用层…...
ubuntu搭建nfs服务centos挂载访问
在Ubuntu上设置NFS服务器 在Ubuntu上,你可以使用apt包管理器来安装NFS服务器。打开终端并运行: sudo apt update sudo apt install nfs-kernel-server创建共享目录 创建一个目录用于共享,例如/shared: sudo mkdir /shared sud…...
React hook之useRef
React useRef 详解 useRef 是 React 提供的一个 Hook,用于在函数组件中创建可变的引用对象。它在 React 开发中有多种重要用途,下面我将全面详细地介绍它的特性和用法。 基本概念 1. 创建 ref const refContainer useRef(initialValue);initialValu…...
模型参数、模型存储精度、参数与显存
模型参数量衡量单位 M:百万(Million) B:十亿(Billion) 1 B 1000 M 1B 1000M 1B1000M 参数存储精度 模型参数是固定的,但是一个参数所表示多少字节不一定,需要看这个参数以什么…...
QMC5883L的驱动
简介 本篇文章的代码已经上传到了github上面,开源代码 作为一个电子罗盘模块,我们可以通过I2C从中获取偏航角yaw,相对于六轴陀螺仪的yaw,qmc5883l几乎不会零飘并且成本较低。 参考资料 QMC5883L磁场传感器驱动 QMC5883L磁力计…...
重启Eureka集群中的节点,对已经注册的服务有什么影响
先看答案,如果正确地操作,重启Eureka集群中的节点,对已经注册的服务影响非常小,甚至可以做到无感知。 但如果操作不当,可能会引发短暂的服务发现问题。 下面我们从Eureka的核心工作原理来详细分析这个问题。 Eureka的…...
10-Oracle 23 ai Vector Search 概述和参数
一、Oracle AI Vector Search 概述 企业和个人都在尝试各种AI,使用客户端或是内部自己搭建集成大模型的终端,加速与大型语言模型(LLM)的结合,同时使用检索增强生成(Retrieval Augmented Generation &#…...
省略号和可变参数模板
本文主要介绍如何展开可变参数的参数包 1.C语言的va_list展开可变参数 #include <iostream> #include <cstdarg>void printNumbers(int count, ...) {// 声明va_list类型的变量va_list args;// 使用va_start将可变参数写入变量argsva_start(args, count);for (in…...
Golang——9、反射和文件操作
反射和文件操作 1、反射1.1、reflect.TypeOf()获取任意值的类型对象1.2、reflect.ValueOf()1.3、结构体反射 2、文件操作2.1、os.Open()打开文件2.2、方式一:使用Read()读取文件2.3、方式二:bufio读取文件2.4、方式三:os.ReadFile读取2.5、写…...
给网站添加live2d看板娘
给网站添加live2d看板娘 参考文献: stevenjoezhang/live2d-widget: 把萌萌哒的看板娘抱回家 (ノ≧∇≦)ノ | Live2D widget for web platformEikanya/Live2d-model: Live2d model collectionzenghongtu/live2d-model-assets 前言 网站环境如下,文章也主…...
嵌入式常见 CPU 架构
架构类型架构厂商芯片厂商典型芯片特点与应用场景PICRISC (8/16 位)MicrochipMicrochipPIC16F877A、PIC18F4550简化指令集,单周期执行;低功耗、CIP 独立外设;用于家电、小电机控制、安防面板等嵌入式场景8051CISC (8 位)Intel(原始…...
