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

209. 长度最小的子数组

209. 长度最小的子数组

力扣题目链接(opens new window)

给定一个含有 n 个正整数的数组和一个正整数 s ,找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组,并返回其长度。如果不存在符合条件的子数组,返回 0。

示例:

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

提示:

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

思路

滑动窗口

滑动窗口:不断的调整子序列的起始位置和终止位置,从而得到想要的结果。

在暴力解法中,是一个for循环滑动窗口的起始位置,一个for循环为滑动窗口的终止位置,用两个for循环完成了一个不断搜索区间的过程。

那么滑动窗口如何用一个for循环来完成这个操作呢?
只用一个for循环,那么这个循环的索引,一定是表示 滑动窗口的终止位置。

在本题中实现滑动窗口,主要确定如下三点:

  • 窗口内是什么?
    窗口就是满足其和 ≥ s 的长度最小的连续子数组。
  • 如何移动窗口的起始位置?
    窗口的起始位置如何移动:如果当前窗口的值大于s了,窗口就要向前移动了(也就是该缩小了)。
  • 如何移动窗口的结束位置?
    窗口的结束位置如何移动:窗口的结束位置就是遍历数组的指针,也就是for循环里的索引。

解题的关键在于 窗口的起始位置如何移动,如图所示:

leetcode_209

可以发现滑动窗口的精妙之处在于根据当前子序列和大小的情况,不断调节子序列的起始位置。从而将O(n^2)暴力解法降为O(n)。

class Solution {//方法:滑动窗口public int minSubArrayLen(int target, int[] nums) {int left = 0;//滑动窗口起始位置int sum = 0; //滑动窗口数值之和//结果取整型类型的最大值,便于和遍历的结果比较     int result = Integer.MAX_VALUE;for(int right = 0; right < nums.length; right++){sum += nums[right]; //使用while,每次更新 i(起始位置),并不断比较子序列是否符合条件while(sum >= target){//right - left + 1为子序列(滑动窗口)的长度result = Math.min(result, right - left + 1); sum -= nums[left++]; // 这里体现出滑动窗口的精髓之处,不断变更i(子序列的起始位置)}}// 如果result没有被赋值的话,就返回0,说明没有符合条件的子序列return result == Integer.MAX_VALUE ? 0 : result;}
}
  • 时间复杂度:O(n)
  • 空间复杂度:O(1)

相关文章:

209. 长度最小的子数组

209. 长度最小的子数组 力扣题目链接(opens new window) 给定一个含有 n 个正整数的数组和一个正整数 s &#xff0c;找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组&#xff0c;并返回其长度。如果不存在符合条件的子数组&#xff0c;返回 0。 示例&#xff1a; 输入…...

【数据结构与算法】查找(Search)【详解】

文章目录查找查找概论一、查找的基本概念顺序表查找一、定义二、算法有序表查找一、折半查找二、插值查找三、斐波那契查找线性索引查找一、稠密索引二、分块索引三、倒排索引二叉树排序与平衡二叉树一、二叉排序树1、定义2、二叉排序树的常见操作3、性能分析二、平衡二叉树1、…...

一文学会 Spring MVC 表单标签

✅作者简介&#xff1a;2022年博客新星 第八。热爱国学的Java后端开发者&#xff0c;修心和技术同步精进。 &#x1f34e;个人主页&#xff1a;Java Fans的博客 &#x1f34a;个人信条&#xff1a;不迁怒&#xff0c;不贰过。小知识&#xff0c;大智慧。 &#x1f49e;当前专栏…...

如何在 Windows10 下运行 Tensorflow 的目标检测?

前言 看过很多博主通过 Object Detection 实现了一些皮卡丘捕捉&#xff0c;二维码检测等诸多特定项的目标检测。而我跟着他们的案例来运行的时候&#xff0c;不是 Tensorflow 版本冲突&#xff0c;就是缺少什么包&#xff0c;还有是运行官方 object_detection_tutorial 不展示…...

【jvm系列-04】精通运行时数据区共享区域---堆

JVM系列整体栏目 内容链接地址【一】初识虚拟机与java虚拟机https://blog.csdn.net/zhenghuishengq/article/details/129544460【二】jvm的类加载子系统以及jclasslib的基本使用https://blog.csdn.net/zhenghuishengq/article/details/129610963【三】运行时私有区域之虚拟机栈…...

ctfshow愚人杯 re easy_pyc wp

一、反编译题目pyc文件 题目下载解压后是一个.pyc文件&#xff0c;那就去反编译看看呗&#xff0c;因为之前用过uncompyle6&#xff0c;直接去命令行执行 uncompyle6 -o ez_re.py ez_re.pyc 得到ez_re.py源码一份~ 但是这里我用uncompyle6反编译的结果不知道为啥就出来很多奇…...

Ubuntu18.04 系统中本地代码上传至Gitlab库

主要步骤如下&#xff1a; 设置SSH Key 上传项目 1.创建SSH Key 每次上传可重新设置一个SSH Key或者使用已有SSH Key &#xff08;1&#xff09;创建SSH Key 创建一个新的SSH Key&#xff0c;终端输入以下指令&#xff0c;其中 “xxxxxx163.com” 是邮箱账号&#xff1a; s…...

Leetcode.1665 完成所有任务的最少初始能量

题目链接 Leetcode.1665 完成所有任务的最少初始能量 Rating &#xff1a; 1901 题目描述 给你一个任务数组 tasks&#xff0c;其中 tasks[i] [actuali, minimumi]&#xff1a; actuali是完成第 i 个任务 需要耗费 的实际能量。minimumi是开始第 i 个任务前需要达到的最低能…...

【C++笔试强训】第一天

选择题 解析&#xff1a;在for循环的循环条件(y 123) && (x < 4)中 &#xff0c;&& 表示逻辑与&#xff0c;从左向右判断两边条件是否成立&#xff0c;只有当两边的条件都为真时&#xff0c;这条语句才为真。左边y 123是赋值语句&#xff0c;一直为真&…...

【网络安全软件】上海道宁与Cybereason为您提供未雨绸缪的攻击保护,终结对端点、整个企业以及网络上任何角落的网络攻击

Cybereason可收集 计算机网络内任何活动方面的数据 如运行当中的程序 被用户访问的文件以及 员工及任何获授权使用网络中的计算机人的 键盘输入和鼠标移动情况 Cybereason提供 即时结束网络攻击的精确度 在计算机、移动设备、服务器和云中 到战斗移动的任何地方 一、开…...

基于RK3568的Android11 适配 MIPI 屏幕

文章目录 前言一、mipi接口是什么?二、原理图三、屏幕点亮流程四、屏幕关键参数1.General Specification2. Power on/off sequence3.Timing五、屏幕初始化序列改写如何把原厂给的数据转换为设备需要的时序dcs小知识:初始化时序:退出时序:总结前言 在本小节会学习到如何适配…...

Ubuntu安装python

CentOS 安装 Python3 没什么坑&#xff0c;按照步骤一步步来就可以了。 但 Ubuntu 安装 Python3 的坑却不少&#xff0c;这里总结一下&#xff0c;避免以后继续踩坑。 我用的是 ubuntu16.04&#xff0c;安装最新版本的 Python3.8.3 第1步&#xff1a;安装编译环境 安装之前…...

django 运用pycharm的各种故障汇总(1)

一.用django入门第一个问题:pycharm的[community]社区版-免费开源与[professional]专业版注册收费两个版本:用django只能有[professional]版本便捷、专业; 解决方案的各种学习总结: 1.破解版:网上找了很多资料,基本已经没效果,不要报太大希望; 2.找中间途径然后有:Python 、…...

【设计模式】单例模式Singleton(Java)

文章目录定义类图Java经典实现懒汉Lazy Mode&#xff1a;饿汉Eager Mode&#xff1a;在饿汉下的多线程案例在懒汉下的多线程案例总结定义 单例模式&#xff08;单件模式&#xff09;确保一个类只有一个实例&#xff0c;并提供一个全局访问点。——HeadFirst 单例模式通过过防…...

机器学习中的公平性

文章目录机器学习公平性评估指标群体公平性指标个人公平性指标引起机器学习模型不公平的潜在因素提升机器学习模型公平性的措施机器学习公平性 定义&#xff1a; 机器学习公平性主要研究如何通过解决或缓解“不公平”来增加模型的公平性&#xff0c;以及如何确保模型的输出结果…...

Docker镜像之Docker Compose讲解

文章目录1 docker-compose1.1 compose编排工具简介1.2 安装docker-compose1.3 编排启动镜像1.4 haproxy代理后端docker容器1.5 安装socat 直接操作socket控制haproxy1.6 compose中yml 配置指令参考1.6.1 简单命令1.6.2 build1.6.3 depends_on1.6.4 deploy1.6.5 logging1.6.6 ne…...

蓝桥杯30天真题冲刺|题解报告|第三十天

大家好&#xff0c;我是snippet&#xff0c;今天是我们这次蓝桥省赛前一起刷题的最后一天了&#xff0c;今天打了一场力扣周赛&#xff0c;前面3个题都是有思路的&#xff0c;第三个题只过了一半的案例&#xff0c;后面看完大佬们的题解彻悟&#xff0c;下面是我今天的题解 目录…...

配置 Git Husky 代码提交约束

介绍 Git Husky 是一个可以管理 Git Hooks 的工具&#xff0c;它可以帮助我们在代码提交的时候运行脚本&#xff0c;以确保代码提交符合特定的规范和约定。 在 Git 中&#xff0c;允许在操作特定的事件时执行特定的脚本&#xff0c;这些事件我们称之为 Hooks。 Git Husky 利…...

IntelliJ IDEA 2023.1 最新变化

文章目录IntelliJ IDEA 2023.1 最新变化一. 主要更新1. 新 UI 增强 测试版启用新 UI2. 在项目打开时更早提供 IDE 功能3. 更快地导入 Maven 项目4.后台提交检查5. Spring Security 匹配器和请求映射的导航 Ultimate二. 用户体验1. 全 IDE 缩放2. 保存多个工具窗口布局的选项3. …...

stm32学习笔记-9 USART串口

9 USART串口 文章目录9 USART串口9.1 串口通信协议9.2 stm32的片上外设-USART9.3 USART收发相关实验9.3.1 实验1&#xff1a;串口发送9.3.2 实验2&#xff1a;移植printf函数9.3.3 实验3&#xff1a;串口发送接收9.4 USART串口数据包9.5 USART数据包相关实验9.5.1 实验1&#x…...

铭豹扩展坞 USB转网口 突然无法识别解决方法

当 USB 转网口扩展坞在一台笔记本上无法识别,但在其他电脑上正常工作时,问题通常出在笔记本自身或其与扩展坞的兼容性上。以下是系统化的定位思路和排查步骤,帮助你快速找到故障原因: 背景: 一个M-pard(铭豹)扩展坞的网卡突然无法识别了,扩展出来的三个USB接口正常。…...

【根据当天日期输出明天的日期(需对闰年做判定)。】2022-5-15

缘由根据当天日期输出明天的日期(需对闰年做判定)。日期类型结构体如下&#xff1a; struct data{ int year; int month; int day;};-编程语言-CSDN问答 struct mdata{ int year; int month; int day; }mdata; int 天数(int year, int month) {switch (month){case 1: case 3:…...

Python爬虫(一):爬虫伪装

一、网站防爬机制概述 在当今互联网环境中&#xff0c;具有一定规模或盈利性质的网站几乎都实施了各种防爬措施。这些措施主要分为两大类&#xff1a; 身份验证机制&#xff1a;直接将未经授权的爬虫阻挡在外反爬技术体系&#xff1a;通过各种技术手段增加爬虫获取数据的难度…...

现代密码学 | 椭圆曲线密码学—附py代码

Elliptic Curve Cryptography 椭圆曲线密码学&#xff08;ECC&#xff09;是一种基于有限域上椭圆曲线数学特性的公钥加密技术。其核心原理涉及椭圆曲线的代数性质、离散对数问题以及有限域上的运算。 椭圆曲线密码学是多种数字签名算法的基础&#xff0c;例如椭圆曲线数字签…...

什么是EULA和DPA

文章目录 EULA&#xff08;End User License Agreement&#xff09;DPA&#xff08;Data Protection Agreement&#xff09;一、定义与背景二、核心内容三、法律效力与责任四、实际应用与意义 EULA&#xff08;End User License Agreement&#xff09; 定义&#xff1a; EULA即…...

2023赣州旅游投资集团

单选题 1.“不登高山&#xff0c;不知天之高也&#xff1b;不临深溪&#xff0c;不知地之厚也。”这句话说明_____。 A、人的意识具有创造性 B、人的认识是独立于实践之外的 C、实践在认识过程中具有决定作用 D、人的一切知识都是从直接经验中获得的 参考答案: C 本题解…...

JS设计模式(4):观察者模式

JS设计模式(4):观察者模式 一、引入 在开发中&#xff0c;我们经常会遇到这样的场景&#xff1a;一个对象的状态变化需要自动通知其他对象&#xff0c;比如&#xff1a; 电商平台中&#xff0c;商品库存变化时需要通知所有订阅该商品的用户&#xff1b;新闻网站中&#xff0…...

浪潮交换机配置track检测实现高速公路收费网络主备切换NQA

浪潮交换机track配置 项目背景高速网络拓扑网络情况分析通信线路收费网络路由 收费汇聚交换机相应配置收费汇聚track配置 项目背景 在实施省内一条高速公路时遇到的需求&#xff0c;本次涉及的主要是收费汇聚交换机的配置&#xff0c;浪潮网络设备在高速项目很少&#xff0c;通…...

Go 并发编程基础:通道(Channel)的使用

在 Go 中&#xff0c;Channel 是 Goroutine 之间通信的核心机制。它提供了一个线程安全的通信方式&#xff0c;用于在多个 Goroutine 之间传递数据&#xff0c;从而实现高效的并发编程。 本章将介绍 Channel 的基本概念、用法、缓冲、关闭机制以及 select 的使用。 一、Channel…...

GitFlow 工作模式(详解)

今天再学项目的过程中遇到使用gitflow模式管理代码&#xff0c;因此进行学习并且发布关于gitflow的一些思考 Git与GitFlow模式 我们在写代码的时候通常会进行网上保存&#xff0c;无论是github还是gittee&#xff0c;都是一种基于git去保存代码的形式&#xff0c;这样保存代码…...