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

leetcode 209. 长度最小的子数组

题目链接:leetcode 209

1.题目

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

找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ,并返回其长度。如果不存在符合条件的子数组,返回 0 。

2.示例

1)示例 1:
输入:target = 7, nums = [2,3,1,2,4,3]
输出:2
解释:子数组 [4,3] 是该条件下的长度最小的子数组。

2)示例 2:
输入:target = 4, nums = [1,4,4]
输出:1

3)示例 3:
输入:target = 11, nums = [1,1,1,1,1,1,1,1]
输出:0

4)数据范围:
1 <= target <= 109
1 <= nums.length <= 105
1 <= nums[i] <= 105

3.分析

首先使用前缀和数组进行记录,对于固定区间某个右端点st2,当sum[st2]-sum[st1]>target时,说明区间长度可以缩小,st1++,当sum[st2]-sum[st1]<target,说明区间长度需要增加才能满足要求,st1++,同时对于大于上一时刻st2_last的st2_now,st1_last已经是满足sum[st2]-sum[st1]>target的最大st1了,st1之前的不需要遍历,时间复杂度为O(n)

4.代码

class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {//O(n)int sum[100010];for(int i=0;i<nums.size();i++)sum[i+1]=sum[i]+nums[i];int st1=0,st2=1,ans=nums.size();if(sum[nums.size()]<target) return 0;while(st1<st2&&st2<=nums.size()){while(sum[st2]-sum[st1]>target&&st1+1<st2)st1++;while(sum[st2]-sum[st1]<target&&st1-1>=0)st1--;if(sum[st2]-sum[st1]>=target)ans=min(ans,st2-st1);st2++;}return ans;}
};

相关文章:

leetcode 209. 长度最小的子数组

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

《rk3399:各显示接口的dts配置》

这里写目录标题 一、前言二、平台支持的显示接口三、两个VOP支持的最大输出分辨率四、VOPL的dts配置五、VOPB的dts配置六、display_subsystem的配置七、backlight 背光配置八、针对eDP接口的配置 以firefly为例8.1 原生配置8.2 启用eDP屏接口配置九、针对MIPI接口屏的配置 以fi…...

Python数据分析-Pandas

Pandas 个人笔迹&#xff0c;建议不看 import pandas as pd import numpy as npSeries类型 spd.Series([1&#xff0c;3&#xff0c;5&#xff0c;np.nan,6,8],index[a,b,c,d,e]) print(s) # 默认0-n-1&#xff0c;否则用index数组作行标 s.index s.value # array() s[a] &g…...

golang 多线程管理 -- chatGpt

提问&#xff1a; 用golang写一个启动函数 start(n) 和对应的停止函数stopAll(),. start函数功能&#xff1a;启动n个线程&#xff0c;线程循环打印日志&#xff0c;stopAll()函数功能&#xff1a;停止start启动的线程 以下是一个示例的Golang代码&#xff0c;其中包括 start…...

【Math】导数、梯度、雅可比矩阵、黑塞矩阵

导数、梯度、雅可比矩阵、黑塞矩阵都是与求导相关的一些概念&#xff0c;比较容易混淆&#xff0c;本文主要是对它们的使用场景和定义进行区分。 首先需要先明确一些函数的叫法&#xff08;是否多元&#xff0c;以粗体和非粗体进行区分&#xff09;&#xff1a; 一元函数&…...

【C语言】——调试技巧

目录 ​编辑 ①前言 1.什么是Bug&#xff1f; 2.什么是调试&#xff1f; 2.1调试的基本步骤 2.2Release与Debug 3.常用快捷键 4.如何写出好的代码 4.1常见的coding技巧 &#x1f449;assert() &#x1f449;const() const修饰指针: ①前言 调试是每个程序员都…...

【Python】pytorch,CUDA是否可用,查看显卡显存剩余容量

CUDA可用&#xff0c;共有 1 个GPU设备可用。 当前使用的GPU设备索引&#xff1a;0 当前使用的GPU设备名称&#xff1a;NVIDIA T1000 GPU显存总量&#xff1a;4.00 GB 已使用的GPU显存&#xff1a;0.00 GB 剩余GPU显存&#xff1a;4.00 GB PyTorch版本&#xff1a;1.10.1cu102 …...

React16入门到入土

搭建环境 默认你已经安装好 node.js 安装 react 脚手架 学习的过程中&#xff0c;我们采用React官方出的脚手架工具 create-react-app npm install -g create-react-app如果提示没有权限&#xff0c;win 用户可以管理员打开终端&#xff0c;mac 用户 可以在前面加上 sudo …...

【GPT引领前沿】GPT4技术与AI绘图

推荐阅读&#xff1a; 1、遥感云大数据在灾害、水体与湿地领域典型案例实践及GPT模型应用 2、GPT模型支持下的Python-GEE遥感云大数据分析、管理与可视化技术 GPT对于每个科研人员已经成为不可或缺的辅助工具&#xff0c;不同的研究领域和项目具有不同的需求。例如在科研编程…...

【LeetCode】19. 删除链表的倒数第 N 个结点

19. 删除链表的倒数第 N 个结点&#xff08;中等&#xff09; 方法&#xff1a;快慢指针 思路 为了找到倒数第 n 个节点&#xff0c;我们应该先找到最后一个节点&#xff0c;然后从它开始往前数 n-1 个节点就是要删除的节点。 对于一般情况&#xff1a;设置 fast 和 slow 两个…...

spring boot3.x集成swagger出现Type javax.servlet.http.HttpServletRequest not present

1. 问题出现原因 spring boot3.x版本依赖于jakarta依赖包&#xff0c;但是swagger依赖底层应用的javax依赖包&#xff0c;所以只要已启动就会报错。 2. 解决方案 移除swagger2依赖 <dependency><groupId>io.springfox</groupId><artifactId>springfo…...

《低代码指南》——智能化低代码开发实践案例

大模型能通过自然语言理解自动生成需求文档及代码供给低代码开发者使用&#xff0c;也具备自动检测和修复代码错误、自动优化代码、找出冗余并提供高效方案等自动化能力&#xff0c;为开发者带来需求模式、设计模式、开发模式的变化&#xff0c;节省时间成本、代码质量更优、进…...

268_C++_字节计算(((bits) + 7) / 8)、字节对齐(((number) + 3) / 4 * 4)

这段代码中包含了两个宏的定义,它们似乎用于进行位操作和字节对齐操作。让我们逐个来解析这两个宏: BITS_TO_BYTES(bits) 宏:#define BITS_TO_BYTES(bits) (((bits) + 7) / 8)这个宏的作用是将位数(bits)转换为字节数(bytes)。它的计算方式是将位数加上7,然后除以8,这…...

JavaWeb知识梳理(后端部分)

JavaWeb 静态web资源&#xff08;如html 页面&#xff09;&#xff1a;指web页面中供人们浏览的数据始终是不变。 动态web资源&#xff1a;指web页面中供人们浏览的数据是由程序产生的&#xff0c;不同时间点访问web页面看到的内容各不相同。 静态web资源开发技术&#xff1…...

AI:07-基于卷积神经网络的海洋生物的识别

当涉及海洋生物的识别和研究时,基于深度学习的方法已经展现出了巨大的潜力。深度学习模型可以利用大量的图像和标记数据来自动学习特征,并实现高准确度的分类任务。本文将介绍如何使用深度学习技术来实现海洋生物的自动识别,并提供相应的代码示例。 数据收集和预处理 要训…...

centos7下docker设置新的下载镜像源并调整存放docker下载镜像的仓库位置

目录 1.设置镜像源 2.调整存放下载镜像的仓库位置 1.设置镜像源 在 /etc/docker下创建一个daemon.json文件。在json中下入 "registry-mirrors": ["https://docker.mirrors.ustc.edu.cn/"] 完成配置 加载配置 systemctl daemon-reload 重启docker sy…...

Gitea--私有git服务器搭建详细教程

一.官方文档 https://docs.gitea.com/zh-cn/说明 gitea 是一个自己托管的Git服务程序。他和GitHub, Gitlab等比较类似。他是从 Gogs 发展而来&#xff0c;gitea的创作团队重新fork了代码&#xff0c;并命名为giteagitea 功能特性多&#xff0c;能够满足我们所有的的代码管理需…...

SOLIDWORKS放样是什么意思?

SOLIDWORKS是一款广受欢迎的三维计算机辅助设计&#xff08;CAD&#xff09;软件&#xff0c;提供了许多强大的功能来帮助工程师实现他们的创意。其中一个重要的功能是放样功能&#xff0c;它在设计过程中起着至关重要的作用。本文将介绍SOLIDWORKS放样的概念、特点和应用。 放…...

Xcode打包ipa文件,查看app包内文件

1、Xcode发布ipa文件前&#xff0c;在info中打开如下两个选项&#xff0c;即可在手机上查看app包名文件夹下的文件及数据。...

AJAX学习笔记6 JQuery对AJAX进行封装

AJAX学习笔记5同步与异步理解_biubiubiu0706的博客-CSDN博客 AJAX请求相关的代码都是类似的&#xff0c;有很多重复的代码&#xff0c;这些重复的代码能不能不写&#xff0c;能不能封装一个工具类。要发送ajax请求的话&#xff0c;就直接调用这个工具类中的相关函数即可。 用J…...

Android Wi-Fi 连接失败日志分析

1. Android wifi 关键日志总结 (1) Wi-Fi 断开 (CTRL-EVENT-DISCONNECTED reason3) 日志相关部分&#xff1a; 06-05 10:48:40.987 943 943 I wpa_supplicant: wlan0: CTRL-EVENT-DISCONNECTED bssid44:9b:c1:57:a8:90 reason3 locally_generated1解析&#xff1a; CTR…...

Cursor实现用excel数据填充word模版的方法

cursor主页&#xff1a;https://www.cursor.com/ 任务目标&#xff1a;把excel格式的数据里的单元格&#xff0c;按照某一个固定模版填充到word中 文章目录 注意事项逐步生成程序1. 确定格式2. 调试程序 注意事项 直接给一个excel文件和最终呈现的word文件的示例&#xff0c;…...

docker详细操作--未完待续

docker介绍 docker官网: Docker&#xff1a;加速容器应用程序开发 harbor官网&#xff1a;Harbor - Harbor 中文 使用docker加速器: Docker镜像极速下载服务 - 毫秒镜像 是什么 Docker 是一种开源的容器化平台&#xff0c;用于将应用程序及其依赖项&#xff08;如库、运行时环…...

从WWDC看苹果产品发展的规律

WWDC 是苹果公司一年一度面向全球开发者的盛会&#xff0c;其主题演讲展现了苹果在产品设计、技术路线、用户体验和生态系统构建上的核心理念与演进脉络。我们借助 ChatGPT Deep Research 工具&#xff0c;对过去十年 WWDC 主题演讲内容进行了系统化分析&#xff0c;形成了这份…...

Go 语言接口详解

Go 语言接口详解 核心概念 接口定义 在 Go 语言中&#xff0c;接口是一种抽象类型&#xff0c;它定义了一组方法的集合&#xff1a; // 定义接口 type Shape interface {Area() float64Perimeter() float64 } 接口实现 Go 接口的实现是隐式的&#xff1a; // 矩形结构体…...

令牌桶 滑动窗口->限流 分布式信号量->限并发的原理 lua脚本分析介绍

文章目录 前言限流限制并发的实际理解限流令牌桶代码实现结果分析令牌桶lua的模拟实现原理总结&#xff1a; 滑动窗口代码实现结果分析lua脚本原理解析 限并发分布式信号量代码实现结果分析lua脚本实现原理 双注解去实现限流 并发结果分析&#xff1a; 实际业务去理解体会统一注…...

大模型多显卡多服务器并行计算方法与实践指南

一、分布式训练概述 大规模语言模型的训练通常需要分布式计算技术,以解决单机资源不足的问题。分布式训练主要分为两种模式: 数据并行:将数据分片到不同设备,每个设备拥有完整的模型副本 模型并行:将模型分割到不同设备,每个设备处理部分模型计算 现代大模型训练通常结合…...

拉力测试cuda pytorch 把 4070显卡拉满

import torch import timedef stress_test_gpu(matrix_size16384, duration300):"""对GPU进行压力测试&#xff0c;通过持续的矩阵乘法来最大化GPU利用率参数:matrix_size: 矩阵维度大小&#xff0c;增大可提高计算复杂度duration: 测试持续时间&#xff08;秒&…...

自然语言处理——循环神经网络

自然语言处理——循环神经网络 循环神经网络应用到基于机器学习的自然语言处理任务序列到类别同步的序列到序列模式异步的序列到序列模式 参数学习和长程依赖问题基于门控的循环神经网络门控循环单元&#xff08;GRU&#xff09;长短期记忆神经网络&#xff08;LSTM&#xff09…...

【碎碎念】宝可梦 Mesh GO : 基于MESH网络的口袋妖怪 宝可梦GO游戏自组网系统

目录 游戏说明《宝可梦 Mesh GO》 —— 局域宝可梦探索Pokmon GO 类游戏核心理念应用场景Mesh 特性 宝可梦玩法融合设计游戏构想要素1. 地图探索&#xff08;基于物理空间 广播范围&#xff09;2. 野生宝可梦生成与广播3. 对战系统4. 道具与通信5. 延伸玩法 安全性设计 技术选…...