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

LeetCode 209 Minimum Size Subarray Sum 题目解析和python代码

题目
Given an array of positive integers nums and a positive integer target, return the minimal length of a
subarray
whose sum is greater than or equal to target. If there is no such subarray, return 0 instead.

Example 1:

Input: target = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: The subarray [4,3] has the minimal length under the problem constraint.
Example 2:

Input: target = 4, nums = [1,4,4]
Output: 1
Example 3:

Input: target = 11, nums = [1,1,1,1,1,1,1,1]
Output: 0

Constraints:

1 <= target <= 109
1 <= nums.length <= 105
1 <= nums[i] <= 104

Follow up: If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log(n)).

题目解析
这里我们可以使用 sliding window 的技巧。
我们可以使用两个 pointers,一个是 start 一个是 end,两个指针都从array的开头开始。
向右移动 end 指针来提高 window 的大小,每一次移动指针都把 nums[end] 添加到现在的和。
当这个和大于或等于 target 时,我们要开始缩短 subarray 的长度。于是我们开始移动 start 这个指针来缩小 window 的大小。通过不停的向右移动 start 指针,直到找到最短的 subarray 的长度。

class Solution:def minSubArrayLen(self, target: int, nums: List[int]) -> int:start = 0curr_sum = 0min_len = float('inf')for end in range(len(nums)):curr_sum += nums[end]while curr_sum >= target:min_len = min(min_len, end - start + 1)curr_sum -= nums[start]start += 1return min_len if min_len != float('inf') else 0

Time complexity 是 O(n)。
Space complexity 是 O(1)。

相关文章:

LeetCode 209 Minimum Size Subarray Sum 题目解析和python代码

题目&#xff1a; Given an array of positive integers nums and a positive integer target, return the minimal length of a subarray whose sum is greater than or equal to target. If there is no such subarray, return 0 instead. Example 1: Input: target 7, nu…...

C# 入坑JAVA 潜规则 注解 列表 listMch,该列表存储了一个映射(Map)的集合 等 入门系列3

java 项目结构 文件说明 潜规则 java入门-CSDN博客 C# 入坑JAVA 潜规则 大小写敏感文件名和类名 枚举等 入门系列2-CSDN博客 java注解 好像和C# 特性 差不多 Data Builder NoArgsConstructor AllArgsConstructor 在Java中&#xff0c;Data、Builder、NoArgsConstructor和Al…...

2024年9月个人工作生活总结

本文为 2024年9月工作生活总结。 研发编码 vuepress构建的几个问题 某vuepress项目&#xff0c;是我在3年多以前自行构想自行着手搞的&#xff0c;主要用于将一些常用的数据文件&#xff08;markdown样式&#xff09;渲染成html网页文件&#xff0c;在自建服务程序里开启访问…...

JVM有哪些参数以及如何使用

JVM&#xff08;Java虚拟机&#xff09;参数用于调整和优化Java应用程序的性能和行为。这些参数主要分为标准参数、非标准参数&#xff08;以-X开头&#xff09;和高级参数&#xff08;以-XX开头&#xff09;。以下是一些常见的JVM参数及其使用方法&#xff1a; 标准参数 -se…...

STM32编码器接口解析及抗噪声措施探讨

1. 引言 在现代控制系统中&#xff0c;编码器扮演着非常重要的角色。它就像一个精密的测量工具&#xff0c;可以告诉我们机械部件的位置和运动状态。在STM32微控制器中&#xff0c;编码器接口可以轻松地与各种编码器连接&#xff0c;实现精确的控制。我将在这里探讨STM32编码器…...

微软发布Windows 11 2024更新,新型Copilot+ AI PC功能亮相

前言 微软在Windows 11的2024更新中加强了对人工智能的应用&#xff0c;推出了新功能Copilot。 此次更新的版本号为26100.1742&#xff0c;Copilot将首先在Windows Insider中推出&#xff0c;计划于11月向特定设备和市场推广&#xff0c;用户需开启“尽快获取最新更新”选项以…...

鹏哥C语言68-70---位操作符+单目操作符+关系操作符

#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <string.h> #include <time.h> //--------------------------------------------------------------------------------------------------------4.位操作符 // &----按&#xff08;2进制…...

showdoc二次开发

showdoc用的vue版本老&#xff0c;需要安装老版本nodejs&#xff0c;比如node 14.21.3 win32-x64-93_binding.node问题 https://github.com/sass/node-sass/releases 下载 web_src\node_modules\node-sass\vendor\win32-x64-93 下面重命名为binding.node 代理到php后端&…...

力扣16~20题

题16&#xff08;中等&#xff09;&#xff1a; 思路&#xff1a; 双指针法&#xff0c;和15题差不多&#xff0c;就是要排除了&#xff0c;如果total<target则排除了更小的&#xff08;left右移&#xff09;&#xff0c;如果total>target则排除了更大的&#xff08;rig…...

Pikachu-Sql-Inject -基于boolian的盲注

基于boolean的盲注: 1、没有报错信息显示&#xff1b; 2、不管是正确的输入&#xff0c;还是错误的输入&#xff0c;都只显示两种情况&#xff0c;true or false&#xff1b; 3、在正确的输入下&#xff0c;输入and 1 1/and 1 2发现可以判断&#xff1b; 布尔盲注常用函数&…...

最后30天,你的系统集成项目管理工程师备考进度到哪儿了?

十一长假归来好&#xff01; 此次归来之后&#xff0c;2024年下半年软考倒计时就从4字头切换到了3字头&#xff0c;今天距离考试还有32天&#xff01; 那么问题来了&#xff0c;临近考试还有30天左右的时候&#xff0c;你的备考进度到哪里了呢&#xff1f; 其实无论目前你的实际…...

网络安全事件的发生,主要原因是什么

网络安全事件的发生&#xff0c;主要原因涉及多个方面&#xff0c;包括技术漏洞、人为因素、经济利益驱动、恶意软件和病毒威胁、社会工程学攻击、内部人员恶意行为、供应链安全问题以及法律法规的不完善等。以下是对这些原因的详细分析&#xff1a; 技术漏洞&#xff1a; 软件…...

【leetcode】274.H指数

为了方便&#xff0c;将 citations 记为 cs。 所谓的 h 指数是指一个具体的数值&#xff0c;该数值为“最大”的满足「至少发表了 x 篇论文&#xff0c;且每篇论文至少被引用 x 次」定义的合法数&#xff0c;重点是“最大”。 用题面的实例 1 来举个 &#x1f330;&#xff0…...

1.Python 引入(字面量、注释、变量、数据类型、数据类型转换、标识符、运算符、字符串扩展)

一、字面量 1、基本介绍 在代码中&#xff0c;被写直接下来的、不需要通过变量存储的值&#xff0c;称之为字面量 2、常用值类型 类型说明数字&#xff08;Number&#xff09;整数&#xff08;int&#xff09;&#xff0c;例如&#xff1a;10、-10浮点数&#xff08;float&…...

【AI知识点】梯度消失(Vanishing Gradient)和梯度爆炸(Exploding Gradient)

梯度消失&#xff08;Vanishing Gradient&#xff09; 和梯度爆炸&#xff08;Exploding Gradient&#xff09; 是神经网络训练中的常见问题&#xff0c;特别是在深层神经网络&#xff08;DNN&#xff09;或递归神经网络&#xff08;RNN&#xff09;中。这两者主要与反向传播算…...

在 ArkTS 网络请求中,重新封装一下 http 模块

在ArkTS中&#xff0c;重新封装http模块可以提供一个更简洁、更易于使用的API&#xff0c;同时隐藏底层细节&#xff0c;使开发者能够更专注于业务逻辑。以下是一个简单的示例&#xff0c;展示了如何重新封装鸿蒙系统的kit.NetworkKit中的http模块&#xff1a; // 创建一个新的…...

Microsoft 更新 Copilot AI,未來將能使用語音並看到你瀏覽的網頁

不過受到 Recall 事件的影響&#xff0c;更新的推出將更緩慢謹慎。 Microsoft 也同步對其網頁版及行動版的 Copilot AI 進行大改版。這主要是為網頁版換上了一個較為簡單乾淨的介面&#xff0c;並增加了一些新的功能&#xff0c;像是 Copilot Voice 能讓你與 AI 助手進行對話式…...

系统架构设计师-论文题(2021年下半年)

1.试题一 论面向方面的编程技术及其应用针对应用开发所面临的规模不断扩大、复杂度不断提升的问题&#xff0c;面向方面的编程Aspect Oriented Programming,AOP技术提供了一种有效的程序开发方法。为了理解和完成一个复杂的程序&#xff0c;通常要把程序进行功能划分和封装。一…...

selenium的webdriver常用方法和属性介绍(2)

selenium的webdriver介绍 从selenium导入webdriver模块&#xff0c;在pycharm中跳转webdriver模块的__init__.py文件&#xff0c;内容如图所示&#xff1a;从selenium包的子目录中导入了很多模块并做了重命名&#xff0c;用于支持如下 Chrome/Edge/Ie/Firefox/Safari浏览器。 使…...

73.【C语言】C/C++的内存区域划分

目录 1.内存里的几个区域 2.示意图 3.解释 1.内存里的几个区域 除了耳熟能详的栈区,堆区,静态区,还有内核空间,内存映射段,数据段,代码段 2.示意图 3.解释 栈区(stack area):局部变量,函数参数,返回数据,返回地址 内存映射段:将文件映射到内存 映射的含义: 如果看过李忠…...

【CSS position 属性】static、relative、fixed、absolute 、sticky详细介绍,多层嵌套定位示例

文章目录 ★ position 的五种类型及基本用法 ★ 一、position 属性概述 二、position 的五种类型详解(初学者版) 1. static(默认值) 2. relative(相对定位) 3. absolute(绝对定位) 4. fixed(固定定位) 5. sticky(粘性定位) 三、定位元素的层级关系(z-i…...

C# 类和继承(抽象类)

抽象类 抽象类是指设计为被继承的类。抽象类只能被用作其他类的基类。 不能创建抽象类的实例。抽象类使用abstract修饰符声明。 抽象类可以包含抽象成员或普通的非抽象成员。抽象类的成员可以是抽象成员和普通带 实现的成员的任意组合。抽象类自己可以派生自另一个抽象类。例…...

SiFli 52把Imagie图片,Font字体资源放在指定位置,编译成指定img.bin和font.bin的问题

分区配置 (ptab.json) img 属性介绍&#xff1a; img 属性指定分区存放的 image 名称&#xff0c;指定的 image 名称必须是当前工程生成的 binary 。 如果 binary 有多个文件&#xff0c;则以 proj_name:binary_name 格式指定文件名&#xff0c; proj_name 为工程 名&…...

【MATLAB代码】基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),附源代码|订阅专栏后可直接查看

文章所述的代码实现了基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),针对传感器观测数据中存在的脉冲型异常噪声问题,通过非线性加权机制提升滤波器的抗干扰能力。代码通过对比传统KF与MCC-KF在含异常值场景下的表现,验证了后者在状态估计鲁棒性方面的显著优…...

全面解析数据库:从基础概念到前沿应用​

在数字化时代&#xff0c;数据已成为企业和社会发展的核心资产&#xff0c;而数据库作为存储、管理和处理数据的关键工具&#xff0c;在各个领域发挥着举足轻重的作用。从电商平台的商品信息管理&#xff0c;到社交网络的用户数据存储&#xff0c;再到金融行业的交易记录处理&a…...

深入解析光敏传感技术:嵌入式仿真平台如何重塑电子工程教学

一、光敏传感技术的物理本质与系统级实现挑战 光敏电阻作为经典的光电传感器件&#xff0c;其工作原理根植于半导体材料的光电导效应。当入射光子能量超过材料带隙宽度时&#xff0c;价带电子受激发跃迁至导带&#xff0c;形成电子-空穴对&#xff0c;导致材料电导率显著提升。…...

【Java多线程从青铜到王者】单例设计模式(八)

wait和sleep的区别 我们的wait也是提供了一个还有超时时间的版本&#xff0c;sleep也是可以指定时间的&#xff0c;也就是说时间一到就会解除阻塞&#xff0c;继续执行 wait和sleep都能被提前唤醒(虽然时间还没有到也可以提前唤醒)&#xff0c;wait能被notify提前唤醒&#xf…...

__VUE_PROD_HYDRATION_MISMATCH_DETAILS__ is not explicitly defined.

这个警告表明您在使用Vue的esm-bundler构建版本时&#xff0c;未明确定义编译时特性标志。以下是详细解释和解决方案&#xff1a; ‌问题原因‌&#xff1a; 该标志是Vue 3.4引入的编译时特性标志&#xff0c;用于控制生产环境下SSR水合不匹配错误的详细报告1使用esm-bundler…...

比较数据迁移后MySQL数据库和ClickHouse数据仓库中的表

设计一个MySQL数据库和Clickhouse数据仓库的表数据比较的详细程序流程,两张表是相同的结构,都有整型主键id字段,需要每次从数据库分批取得2000条数据,用于比较,比较操作的同时可以再取2000条数据,等上一次比较完成之后,开始比较,直到比较完所有的数据。比较操作需要比较…...

DriveGPT4: Interpretable End-to-end Autonomous Driving via Large Language Model

一、研究背景与创新点 (一)现有方法的局限性 当前智驾系统面临两大核心挑战:一是长尾问题,即系统在遇到新场景时可能失效,例如突发交通状况或非常规道路环境;二是可解释性问题,传统方法无法解释智驾系统的决策过程,用户难以理解车辆行为的依据。传统语言模型(如 BERT…...