当前位置: 首页 > 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的功…...

利用最小二乘法找圆心和半径

#include <iostream> #include <vector> #include <cmath> #include <Eigen/Dense> // 需安装Eigen库用于矩阵运算 // 定义点结构 struct Point { double x, y; Point(double x_, double y_) : x(x_), y(y_) {} }; // 最小二乘法求圆心和半径 …...

三维GIS开发cesium智慧地铁教程(5)Cesium相机控制

一、环境搭建 <script src"../cesium1.99/Build/Cesium/Cesium.js"></script> <link rel"stylesheet" href"../cesium1.99/Build/Cesium/Widgets/widgets.css"> 关键配置点&#xff1a; 路径验证&#xff1a;确保相对路径.…...

FastAPI 教程:从入门到实践

FastAPI 是一个现代、快速&#xff08;高性能&#xff09;的 Web 框架&#xff0c;用于构建 API&#xff0c;支持 Python 3.6。它基于标准 Python 类型提示&#xff0c;易于学习且功能强大。以下是一个完整的 FastAPI 入门教程&#xff0c;涵盖从环境搭建到创建并运行一个简单的…...

LeetCode - 394. 字符串解码

题目 394. 字符串解码 - 力扣&#xff08;LeetCode&#xff09; 思路 使用两个栈&#xff1a;一个存储重复次数&#xff0c;一个存储字符串 遍历输入字符串&#xff1a; 数字处理&#xff1a;遇到数字时&#xff0c;累积计算重复次数左括号处理&#xff1a;保存当前状态&a…...

高等数学(下)题型笔记(八)空间解析几何与向量代数

目录 0 前言 1 向量的点乘 1.1 基本公式 1.2 例题 2 向量的叉乘 2.1 基础知识 2.2 例题 3 空间平面方程 3.1 基础知识 3.2 例题 4 空间直线方程 4.1 基础知识 4.2 例题 5 旋转曲面及其方程 5.1 基础知识 5.2 例题 6 空间曲面的法线与切平面 6.1 基础知识 6.2…...

vue3+vite项目中使用.env文件环境变量方法

vue3vite项目中使用.env文件环境变量方法 .env文件作用命名规则常用的配置项示例使用方法注意事项在vite.config.js文件中读取环境变量方法 .env文件作用 .env 文件用于定义环境变量&#xff0c;这些变量可以在项目中通过 import.meta.env 进行访问。Vite 会自动加载这些环境变…...

全志A40i android7.1 调试信息打印串口由uart0改为uart3

一&#xff0c;概述 1. 目的 将调试信息打印串口由uart0改为uart3。 2. 版本信息 Uboot版本&#xff1a;2014.07&#xff1b; Kernel版本&#xff1a;Linux-3.10&#xff1b; 二&#xff0c;Uboot 1. sys_config.fex改动 使能uart3(TX:PH00 RX:PH01)&#xff0c;并让boo…...

优选算法第十二讲:队列 + 宽搜 优先级队列

优选算法第十二讲&#xff1a;队列 宽搜 && 优先级队列 1.N叉树的层序遍历2.二叉树的锯齿型层序遍历3.二叉树最大宽度4.在每个树行中找最大值5.优先级队列 -- 最后一块石头的重量6.数据流中的第K大元素7.前K个高频单词8.数据流的中位数 1.N叉树的层序遍历 2.二叉树的锯…...

人机融合智能 | “人智交互”跨学科新领域

本文系统地提出基于“以人为中心AI(HCAI)”理念的人-人工智能交互(人智交互)这一跨学科新领域及框架,定义人智交互领域的理念、基本理论和关键问题、方法、开发流程和参与团队等,阐述提出人智交互新领域的意义。然后,提出人智交互研究的三种新范式取向以及它们的意义。最后,总结…...

Kafka入门-生产者

生产者 生产者发送流程&#xff1a; 延迟时间为0ms时&#xff0c;也就意味着每当有数据就会直接发送 异步发送API 异步发送和同步发送的不同在于&#xff1a;异步发送不需要等待结果&#xff0c;同步发送必须等待结果才能进行下一步发送。 普通异步发送 首先导入所需的k…...