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

Leetcode经典题20--长度最小的子数组

题目描述

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

找出该数组中满足其总和大于等于 target 的长度最小的子数组

[numsl, numsl+1, ..., numsr-1, numsr] ,并返回其长度。如果不存在符合条件的子数组,返回 0 。

输入输出示例

输入:target = 7, nums = [2,3,1,2,4,3]

输出:2

解释:子数组 [4,3] 是该条件下的长度最小的子数组。

解决方案

方式一:滑动窗口
算法思想

定义两个指针 start 和 end 分别表示子数组(滑动窗口窗口)的开始位置和结束位置,维护变量 sum 存储子数组中的元素和(即从 nums[start] 到 nums[end] 的元素和)。

初始状态下,start 和 end 都指向下标 0,sum 的值为 0。

每一轮迭代,将 nums[end] 加到 sum,如果 sum≥s,则更新子数组的最小长度(此时子数组的长度是 end−start+1),然后将 nums[start] 从 sum 中减去并将 start 右移,直到 sum

实现代码
class Solution {public int minSubArrayLen(int target, int[] nums) {int n=nums.length;if(n==0){return 0;}int ans=Integer.MAX_VALUE;int start=0,end=0;//窗口的左边界和右边界int sum=0;//窗口的元素和while(end<n){//向右滑动sum+=nums[end];//当窗口内的元素和大于等于目标值,缩小窗口while(sum>=target){ans=Math.min(ans,end-start+1);sum-=nums[start];start++;}//否则扩大窗口end++;}//考虑达不到目标值的情况return ans==Integer.MAX_VALUE?0:ans;}
}
复杂度分析

时间复杂度:O(n),其中 n 是数组的长度。指针 start 和 end 最多各移动 n 次。

空间复杂度:O(1)。

相关文章:

Leetcode经典题20--长度最小的子数组

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

【计算机视觉】超简单!维纳滤波的经典案例

Hey小伙伴们&#xff01;今天来给大家分享一个 计算机视觉 中非常经典且实用的技术——维纳滤波&#xff08;Wiener Filter&#xff09;。维纳滤波是一种基于最小均方误差准则的滤波方法&#xff0c;广泛应用于图像去噪、模糊恢复等领域。它不仅可以有效去除图像中的噪声&#…...

【closerAI ComfyUI】快速洗图!高效快速的提示词反推节点——cliption,让洗图出图快人一步不爆显存!

添加图片注释,不超过 140 字(可选) 【closerAI ComfyUI】快速洗图!高效快速的提示词反推节点——cliption,让洗图出图快人一步不爆显存! 大家好,我是Jimmy。反推提示词的节点有很多,像Florence2 、Joycaption2、喵手等。都是非常优秀的。但是呢,就是占用设备资源,加…...

AE Dressler CESAR 1312 Generator Model User Manual

AE Dressler CESAR 1312 Generator Model User Manual...

【513. 找树左下角的值 中等】

题目&#xff1a; 给定一个二叉树的 根节点 root&#xff0c;请找出该二叉树的 最底层 最左边 节点的值。 假设二叉树中至少有一个节点。 示例 1: 输入: root [2,1,3] 输出: 1 示例 2: 输入: [1,2,3,4,null,5,6,null,null,7] 输出: 7 提示: 二叉树的节点个数的范围是 …...

网络通信的瑞士军刀:Python socket库全解析

文章目录 网络通信的瑞士军刀&#xff1a;Python socket库全解析背景库介绍安装与重要性简单库函数使用方法场景应用常见Bug及解决方案总结 网络通信的瑞士军刀&#xff1a;Python socket库全解析 背景 在现代编程中&#xff0c;网络通信是不可或缺的一部分。无论是构建客户端…...

【笔记️】魔爪 Mini mx 使用快捷键

B站教程地址&#xff1a;MOZA魔爪的个人空间-MOZA魔爪个人主页-哔哩哔哩视频 1、开关键: 单击 → 开启录制/拍照 → 再次单击结束&#xff1b;休眠时,单击晚醒 双击 → 切换拍照/录制模式 三击 → 切换横竖拍 长按 → 关机 2、变焦键: 单击 → 切换航向俯仰跟随模式 ( 开机默…...

去除 el-input 输入框的边框(element-ui@2.15.13)

dgqdgqdeMac-mini spid-admin % yarn list --pattern element-ui yarn list v1.22.22 └─ element-ui2.15.13 ✨ Done in 0.23s.dgqdgqdeMac-mini spid-admin % yarn list vue yarn list v1.22.22 warning Filtering by arguments is deprecated. Please use the pattern opt…...

Vue中的一些用法

一、验证规则&#xff1a; 身份证的验证规则&#xff1a; 电话号码的验证规则&#xff1a; 二、选中一项后禁用其他选项&#xff1a; data(){ return{ dataForm{ medicalHistory:[] } }, 三、多选框选择后页面中不显示数据&#xff1a; 在表单提交时加 .join(",&…...

异步爬虫之协程的基本原理

我们知道爬虫是 IO 密集型任务&#xff0c;例如使用 requests 库来爬取某个站点&#xff0c;当发出一个请求后&#xff0c;程序必须等待网站返回响应&#xff0c;才能接着运行&#xff0c;而在等待响应的过程中&#xff0c;整个爬虫程序是一直在等待的&#xff0c;实际上没有做…...

Diffusion Transformer(DiT)——将扩散过程中的U-Net换成ViT:近频繁用于视频生成与机器人动作预测(含清华PAD详解)

前言 本文最开始属于此文《视频生成Sora的全面解析&#xff1a;从AI绘画、ViT到ViViT、TECO、DiT、VDT、NaViT等》 但考虑到DiT除了广泛应用于视频生成领域中&#xff0c;在机器人动作预测也被运用的越来越多&#xff0c;加之DiT确实是一个比较大的创新&#xff0c;影响力大&…...

CPT203 Software Engineering 软件工程 Pt.2 敏捷方法和需求工程(中英双语)

文章目录 3. Aglie methods&#xff08;敏捷方法&#xff09;3.1 Aglie methods&#xff08;敏捷方法&#xff09;3.1.1 特点3.1.2 优点3.1.3 缺点3.1.4 原则3.1.5 计划驱动与敏捷方法的对比 3.2 Scrum3.2.1 Scrum roles3.2.2 Scrum Activities and Artifacts3.2.2.1 Product B…...

【Git】-- 在本地执行 git fetch 发生异常

目录 1、现象 2、解决参考 2.1 检查网络连接 2.2 更新 Git 客户端 2.3 更改 GitHub URL 的访问协议 2.4 禁用 SSL 验证&#xff08;临时解决&#xff09; 2.5 检查系统的 CA 证书 2.6 重新克隆仓库 1、现象 在本地执行 $ git fetch upstream 时&#xff0c;抛出以下…...

Apache Doris 创始人:何为“现代化”的数据仓库?

在 12 月 14 日的 Doris Summit Asia 2024 上&#xff0c;Apache Doris 创始人 & PMC 成员马如悦在开场演讲中&#xff0c;围绕“现代化数据仓库”这一主题&#xff0c;指出 3.0 版本是 Apache Doris 研发路程中的重要里程碑&#xff0c;他将这一进展总结为“实时之路”、“…...

高校网络安全存在的问题与对策研究

目 录 摘 要1 第1章 引言2 1.1研究背景2 1.2研究意义2 第2章系统开发的相关技术简介3 2.1 Spring boot框架3 2.2 MySQL简介3 2.3 Vue框架3 2.4 JAVA简介3 第3章 系统需求分析4 3.1可行性分析4 3.1.1技术可行性4 3.1.2运行可行性4 3.1.3经济可行性5 3.2功能需求…...

Redis的数据类型,线程,持久化机制

1. Redis是单线程还是多线程的&#xff0c;为什么&#xff1f; Redis是单线程的&#xff08;传统实现&#xff09; Redis在传统的实现中是单线程的。尽管它处理的任务很多&#xff0c;但它使用单线程来处理所有客户端的请求。这个设计决策有几个关键原因&#xff1a; 简化模型…...

什么是ondelete cascade以及使用sqlite演示ondelete cascade使用案例

什么是ondelete cascade ‌ON DELETE CASCADE是数据库中的一种约束&#xff0c;用于自动删除相关的记录‌。具体来说&#xff0c;当一个表中的记录&#xff08;父表&#xff09;被删除时&#xff0c;与其相关的其他表&#xff08;子表&#xff09;中的记录也会被自动删除&…...

Java设计模式 —— 【结构型模式】享元模式(Flyweight Pattern) 详解

文章目录 概述结构案例实现优缺点及使用场景 概述 享元模式也叫蝇量模式&#xff1a;运用共享技术有效地支持大量细粒度的对象&#xff1b; 常用于系统底层开发&#xff0c;解决系统的性能问题。像数据库连接池&#xff0c;里面都是创建好的连接对象&#xff0c;在这些连接对象…...

数据的简单处理——pandas模块——选择数据

要对读取的数据进行编辑&#xff0c;需要先学会选择数据的操作&#xff0c;如果选择行数据、列数据或者同时选择行列数据。 ############################## ##作者&#xff1a;白雪公主的后妈 ##时间&#xff1a;2024年12月29日 ##主题&#xff1a;数据的简单处理——pandas模…...

淘宝/天猫购物车商品列表API:深度解析与应用实践

引言 在电商领域&#xff0c;购物车功能是提升用户体验和增加销售额的关键工具。淘宝和天猫作为中国最大的电商平台&#xff0c;提供了丰富的API接口&#xff0c;其中包括获取购物车商品列表的API&#xff0c;即buyer_cart_list。本文将深入解析淘宝/天猫购物车商品列表API的功…...

变量 varablie 声明- Rust 变量 let mut 声明与 C/C++ 变量声明对比分析

一、变量声明设计&#xff1a;let 与 mut 的哲学解析 Rust 采用 let 声明变量并通过 mut 显式标记可变性&#xff0c;这种设计体现了语言的核心哲学。以下是深度解析&#xff1a; 1.1 设计理念剖析 安全优先原则&#xff1a;默认不可变强制开发者明确声明意图 let x 5; …...

零门槛NAS搭建:WinNAS如何让普通电脑秒变私有云?

一、核心优势&#xff1a;专为Windows用户设计的极简NAS WinNAS由深圳耘想存储科技开发&#xff0c;是一款收费低廉但功能全面的Windows NAS工具&#xff0c;主打“无学习成本部署” 。与其他NAS软件相比&#xff0c;其优势在于&#xff1a; 无需硬件改造&#xff1a;将任意W…...

linux之kylin系统nginx的安装

一、nginx的作用 1.可做高性能的web服务器 直接处理静态资源&#xff08;HTML/CSS/图片等&#xff09;&#xff0c;响应速度远超传统服务器类似apache支持高并发连接 2.反向代理服务器 隐藏后端服务器IP地址&#xff0c;提高安全性 3.负载均衡服务器 支持多种策略分发流量…...

全球首个30米分辨率湿地数据集(2000—2022)

数据简介 今天我们分享的数据是全球30米分辨率湿地数据集&#xff0c;包含8种湿地亚类&#xff0c;该数据以0.5X0.5的瓦片存储&#xff0c;我们整理了所有属于中国的瓦片名称与其对应省份&#xff0c;方便大家研究使用。 该数据集作为全球首个30米分辨率、覆盖2000–2022年时间…...

家政维修平台实战20:权限设计

目录 1 获取工人信息2 搭建工人入口3 权限判断总结 目前我们已经搭建好了基础的用户体系&#xff0c;主要是分成几个表&#xff0c;用户表我们是记录用户的基础信息&#xff0c;包括手机、昵称、头像。而工人和员工各有各的表。那么就有一个问题&#xff0c;不同的角色&#xf…...

React19源码系列之 事件插件系统

事件类别 事件类型 定义 文档 Event Event 接口表示在 EventTarget 上出现的事件。 Event - Web API | MDN UIEvent UIEvent 接口表示简单的用户界面事件。 UIEvent - Web API | MDN KeyboardEvent KeyboardEvent 对象描述了用户与键盘的交互。 KeyboardEvent - Web…...

MODBUS TCP转CANopen 技术赋能高效协同作业

在现代工业自动化领域&#xff0c;MODBUS TCP和CANopen两种通讯协议因其稳定性和高效性被广泛应用于各种设备和系统中。而随着科技的不断进步&#xff0c;这两种通讯协议也正在被逐步融合&#xff0c;形成了一种新型的通讯方式——开疆智能MODBUS TCP转CANopen网关KJ-TCPC-CANP…...

PL0语法,分析器实现!

简介 PL/0 是一种简单的编程语言,通常用于教学编译原理。它的语法结构清晰,功能包括常量定义、变量声明、过程(子程序)定义以及基本的控制结构(如条件语句和循环语句)。 PL/0 语法规范 PL/0 是一种教学用的小型编程语言,由 Niklaus Wirth 设计,用于展示编译原理的核…...

Ascend NPU上适配Step-Audio模型

1 概述 1.1 简述 Step-Audio 是业界首个集语音理解与生成控制一体化的产品级开源实时语音对话系统&#xff0c;支持多语言对话&#xff08;如 中文&#xff0c;英文&#xff0c;日语&#xff09;&#xff0c;语音情感&#xff08;如 开心&#xff0c;悲伤&#xff09;&#x…...

涂鸦T5AI手搓语音、emoji、otto机器人从入门到实战

“&#x1f916;手搓TuyaAI语音指令 &#x1f60d;秒变表情包大师&#xff0c;让萌系Otto机器人&#x1f525;玩出智能新花样&#xff01;开整&#xff01;” &#x1f916; Otto机器人 → 直接点明主体 手搓TuyaAI语音 → 强调 自主编程/自定义 语音控制&#xff08;TuyaAI…...