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

【LeetCode】【209】长度最小的子数组(1488字)

文章目录

    • @[toc]
      • 题目描述
      • 样例输入输出与解释
        • 样例1
        • 样例2
        • 样例3
      • 提示
      • 进阶
      • Python实现
        • 前缀和+二分查找
        • 滑动窗口

因上努力

个人主页:丷从心·

系列专栏:LeetCode

刷题指南:LeetCode刷题指南

果上随缘


题目描述

  • 给定一个含有n个正整数的数组和一个正整数target
  • 找出该数组中满足其总和大于等于target的长度最小的连续子数组[numsl, numsl+1, ..., numsr-1, numsr],并返回其长度
  • 如果不存在符合条件的子数组,返回0

样例输入输出与解释

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

提示

  • 1 <= target <= 10^9
  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^5

进阶

  • 如果已经实现O(n)时间复杂度的解法,尝试设计一个O(nlog(n))时间复杂度的解法

Python实现

前缀和+二分查找
class Solution:def minSubArrayLen(self, s: int, nums: List[int]) -> int:n = len(nums)res = n + 1sums = [0]for i in range(n):sums.append(sums[-1] + nums[i])for i in range(1, n + 1):target = sums[i - 1] + sbound = bisect.bisect_left(sums, target)if bound != len(sums):res = min(res, bound - (i - 1))return res if res != n + 1 else 0
滑动窗口
class Solution:def minSubArrayLen(self, target: int, nums: List[int]) -> int:n = len(nums)res, sum = n + 1, 0start, end = 0, 0while end < n:sum += nums[end]while sum >= target:res = min(res, end - start + 1)sum -= nums[start]start += 1end += 1return res if res != n + 1 else 0

相关文章:

【LeetCode】【209】长度最小的子数组(1488字)

文章目录 [toc]题目描述样例输入输出与解释样例1样例2样例3 提示进阶Python实现前缀和二分查找滑动窗口 个人主页&#xff1a;丷从心 系列专栏&#xff1a;LeetCode 刷题指南&#xff1a;LeetCode刷题指南 题目描述 给定一个含有n个正整数的数组和一个正整数target找出该数组…...

1738. 找出第 K 大的异或坐标值

题目&#xff1a; 给你一个二维矩阵 matrix 和一个整数 k &#xff0c;矩阵大小为 m x n 由非负整数组成。 矩阵中坐标 (a, b) 的 值 可由对所有满足 0 < i < a < m 且 0 < j < b < n 的元素 matrix[i][j]&#xff08;下标从 0 开始计数&#xff09;执行异…...

Fortran: stdlib标准库

Fortran 标准库 stdlib_logger,stdlib_error, stdlib_sorting,stdlib_optval模块挺好用 封装 stdlib_logger和stdlib_error: M_logger.F90 module M_loggeruse stdlib_loggeruse stdlib_error containssubroutine info(message,module,procedure)character(len*),intent(in):…...

CSS3优秀动画代码示例

目录 旋转立方体悬停效果动画路径动画纯CSS进度条文字打字机效果3D翻转卡片SVG路径跟随动画SVG心跳动画旋转文字手风琴效果...

嵌入式0基础开始学习 ⅠC语言(4)循环结构

0.问题引入 求0~100数据之和&#xff1a; int sum 0; sum 1234....100; 废手&#xff0c;那么有没有一种好的方法取操作呢&#xff1f; int sum 0; int i 1; sum sum i; // sum 01; …...

【JAVASE】抽象类

1、抽象类概念 在面向对象的概念中&#xff0c;所有的对象都是通过类来描绘的&#xff0c;但是反过来&#xff0c;并不是所有的类都是用来描绘对象的&#xff0c;如果一个类中没有包含足够的信息来描绘一个具体的对象&#xff0c;这样的类就是抽象类。比如&#xff1a; 说明&a…...

嵌入式硬件中PCB走线与过孔的电流承载能力分析

简介 使用FR4敷铜板PCBA上各个器件之间的电气连接是通过其各层敷着的铜箔走线和过孔来实现的。 由于不同产品、不同模块电流大小不同,为实现各个功能,设计人员需要知道所设计的走线和过孔能否承载相应的电流,以实现产品的功能,防止过流时产品烧毁。 文中介绍设计和测试FR4敷…...

动态规划之背包问题中如何确定遍历顺序的问题-组合or排列?

关于如何确定遍历顺序 322. 零钱兑换中&#xff0c;本题求钱币最小个数&#xff0c;那么钱币有顺序和没有顺序都可以&#xff0c;都不影响钱币的最小个数。 所以本题并不强调集合是组合还是排列。 如果求组合数就是外层for循环遍历物品&#xff0c;内层for遍历背包。 如果求…...

开源大模型与闭源大模型

概述 开源大模型和闭源大模型是两种常见的大模型类型&#xff0c;它们在以下方面存在差异&#xff1a; 开放性&#xff1a; 开源大模型&#xff1a;代码和模型结构是公开可用的&#xff0c;任何人都可以访问、修改和使用。闭源大模型&#xff1a;模型的代码和结构是私有的&…...

python+selenium - UI自动框架之封装查找元素

单一的元素定位方法不能满足所有元素的定位&#xff0c;可以根据每个元素的特点来找到合适的方法&#xff0c;可以参考下图的方法&#xff1a; elementFind.py from selenium.webdriver.support.ui import WebDriverWait from selenium.webdriver.support import expected_con…...

java 拦截器-用户无操作超时退出利用Redis

1、授权过滤&#xff0c;只要实现AuthConfigAdapter接口 2、利用Redis token超时时间&#xff0c;用户访问后台续时 效果 Component public class AuthFilter implements Filter {private static Logger logger LoggerFactory.getLogger(AuthFilter.class);Autowiredprivat…...

民国漫画杂志《时代漫画》第16期.PDF

时代漫画16.PDF: https://url03.ctfile.com/f/1779803-1248612470-6a05f0?p9586 (访问密码: 9586) 《时代漫画》的杂志在1934年诞生了&#xff0c;截止1937年6月战争来临被迫停刊共发行了39期。 ps:资源来源网络&#xff01;...

线程池以及日志类的实现

目录 线程池: 日志类: 可变参数以及相关函数 1.va_list 2. va_start 3. va_end 日志Log类 线程池 线程池: 是一种线程使用模式。线程过多会带来调度开销&#xff0c;进而影响缓存局部性和整体性能。而线程池维护着多个线程&#xff0c;等待着 监督管理者分配可并发执行…...

基于长短期记忆网络 LSTM 的送餐时间预测

前言 系列专栏:【深度学习&#xff1a;算法项目实战】✨︎ 涉及医疗健康、财经金融、商业零售、食品饮料、运动健身、交通运输、环境科学、社交媒体以及文本和图像处理等诸多领域&#xff0c;讨论了各种复杂的深度神经网络思想&#xff0c;如卷积神经网络、循环神经网络、生成对…...

K-means聚类算法详细介绍

目录 &#x1f349;简介 &#x1f348;K-means聚类模型详解 &#x1f348;K-means聚类的基本原理 &#x1f348;K-means聚类的算法步骤 &#x1f348;K-means聚类的优缺点 &#x1f34d;优点 &#x1f34d;缺点 &#x1f348;K-means聚类的应用场景 &#x1f348;K-mea…...

SAP FS00如何导出会计总账科目表

输入T-code : S_ALR_87012333 根据‘FS00’中找到的总账科目&#xff0c;进行筛选执行 点击左上角的列表菜单&#xff0c;选择‘电子表格’导出即可...

ROS参数服务器

一、介绍 参数服务器是用于存储和检索参数的分布式多机器人配置系统&#xff0c;它允许节点动态地获取参数值。 在ROS中&#xff0c;参数服务器是一种用于存储和检索参数的分布式多机器人配置系统。它允许节点动态地获取参数值&#xff0c;并提供了一种方便的方式来管理和共享配…...

QCC---DFU升级变更设备名和地址

QCC---DFU升级变更设备名和地址 这个很多人碰到这个疑问,升级了改不了设备名和地址 /******************************************************************************* Copyright (c) 2018 Qualcomm Technologies International, Ltd. FILE NAME sink_dfu_ps.c DESCRIPT…...

[力扣题解] 695. 岛屿的最大面积

题目&#xff1a;695. 岛屿的最大面积 思路 代码 深度优先搜索 // 深度搜索 class Solution { private:int area_max 0;int dir[4][2] {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};void dfs(vector<vector<int>>& grid, vector<vector<bool>>& …...

AI模型发展路径探析:开源与闭源,何者更胜一筹?

AI模型发展路径探析&#xff1a;开源与闭源&#xff0c;何者更胜一筹&#xff1f; 在当今快速发展的人工智能领域&#xff0c;AI模型成为推动技术创新和应用落地的关键。而评价一个AI模型“好不好”“有没有发展”&#xff0c;往往会引向一个重要话题&#xff1a;开源与闭源这…...

Spark 之 入门讲解详细版(1)

1、简介 1.1 Spark简介 Spark是加州大学伯克利分校AMP实验室&#xff08;Algorithms, Machines, and People Lab&#xff09;开发通用内存并行计算框架。Spark在2013年6月进入Apache成为孵化项目&#xff0c;8个月后成为Apache顶级项目&#xff0c;速度之快足见过人之处&…...

Unity3D中Gfx.WaitForPresent优化方案

前言 在Unity中&#xff0c;Gfx.WaitForPresent占用CPU过高通常表示主线程在等待GPU完成渲染&#xff08;即CPU被阻塞&#xff09;&#xff0c;这表明存在GPU瓶颈或垂直同步/帧率设置问题。以下是系统的优化方案&#xff1a; 对惹&#xff0c;这里有一个游戏开发交流小组&…...

PHP和Node.js哪个更爽?

先说结论&#xff0c;rust完胜。 php&#xff1a;laravel&#xff0c;swoole&#xff0c;webman&#xff0c;最开始在苏宁的时候写了几年php&#xff0c;当时觉得php真的是世界上最好的语言&#xff0c;因为当初活在舒适圈里&#xff0c;不愿意跳出来&#xff0c;就好比当初活在…...

循环冗余码校验CRC码 算法步骤+详细实例计算

通信过程&#xff1a;&#xff08;白话解释&#xff09; 我们将原始待发送的消息称为 M M M&#xff0c;依据发送接收消息双方约定的生成多项式 G ( x ) G(x) G(x)&#xff08;意思就是 G &#xff08; x ) G&#xff08;x) G&#xff08;x) 是已知的&#xff09;&#xff0…...

UE5 学习系列(三)创建和移动物体

这篇博客是该系列的第三篇&#xff0c;是在之前两篇博客的基础上展开&#xff0c;主要介绍如何在操作界面中创建和拖动物体&#xff0c;这篇博客跟随的视频链接如下&#xff1a; B 站视频&#xff1a;s03-创建和移动物体 如果你不打算开之前的博客并且对UE5 比较熟的话按照以…...

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

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

2021-03-15 iview一些问题

1.iview 在使用tree组件时&#xff0c;发现没有set类的方法&#xff0c;只有get&#xff0c;那么要改变tree值&#xff0c;只能遍历treeData&#xff0c;递归修改treeData的checked&#xff0c;发现无法更改&#xff0c;原因在于check模式下&#xff0c;子元素的勾选状态跟父节…...

论文浅尝 | 基于判别指令微调生成式大语言模型的知识图谱补全方法(ISWC2024)

笔记整理&#xff1a;刘治强&#xff0c;浙江大学硕士生&#xff0c;研究方向为知识图谱表示学习&#xff0c;大语言模型 论文链接&#xff1a;http://arxiv.org/abs/2407.16127 发表会议&#xff1a;ISWC 2024 1. 动机 传统的知识图谱补全&#xff08;KGC&#xff09;模型通过…...

Linux-07 ubuntu 的 chrome 启动不了

文章目录 问题原因解决步骤一、卸载旧版chrome二、重新安装chorme三、启动不了&#xff0c;报错如下四、启动不了&#xff0c;解决如下 总结 问题原因 在应用中可以看到chrome&#xff0c;但是打不开(说明&#xff1a;原来的ubuntu系统出问题了&#xff0c;这个是备用的硬盘&a…...

《基于Apache Flink的流处理》笔记

思维导图 1-3 章 4-7章 8-11 章 参考资料 源码&#xff1a; https://github.com/streaming-with-flink 博客 https://flink.apache.org/bloghttps://www.ververica.com/blog 聚会及会议 https://flink-forward.orghttps://www.meetup.com/topics/apache-flink https://n…...