[数组二分查找] 0209. 长度最小的子数组

文章目录

      • 1. 题目链接
      • 2. 题目大意
      • 3. 示例
      • 4. 解题思路
      • 5. 参考代码

1. 题目链接

209. 长度最小的子数组 - 力扣(LeetCode)



2. 题目大意

描述:给定一个只包含正整数的数组 nums 和一个正整数 target。

要求:找出数组中满足和大于等于 target 的长度最小的「连续子数组」,
并返回其长度。如果不存在符合条件的子数组,返回 0。

说明

  • 1≤target≤109。
  • 1≤nums.length≤105。
  • 1≤nums[i]≤105。


3. 示例

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


4. 解题思路

最直接的做法是暴力枚举,时间复杂度为 O(n2)。但是我们可以利用滑动窗口的方法,在时间复杂度为 O(n) 的范围内解决问题。

用滑动窗口来记录连续子数组的和,设定两个指针:left、right,分别指向滑动窗口的左右边界,保证窗口中的和刚好大于等于 target。

  1. 一开始,left、right 都指向 0。
  2. 向右移动 right,将最右侧元素加入当前窗口和 window‾sum 中。
  3. 如果 window‾sum≥target,则不断右移 left,缩小滑动窗口长度,并更新窗口和的最小值,直到 window‾sum<target。
  4. 然后继续右移 right,直到 right≥len(nums) 结束。
  5. 输出窗口和的最小值作为答案。


5. 参考代码

class Solution {public int minSubArrayLen(int target, int[] nums) {int size = nums.length;int ans = size + 1; // 初始化为比数组长度大1的值,方便后续判断int left = 0;int right = 0;int windowSum = 0;while (right < size) {windowSum += nums[right];// 当窗口内的和大于等于目标值时,尝试缩小窗口while (windowSum >= target) {ans = Math.min(ans, right - left + 1);windowSum -= nums[left];left++;}right++;}return ans == size + 1 ? 0 : ans;}
}


本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.xdnf.cn/news/20293.html

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

A039-基于SpringBoot的农产品销售系统的设计与实现

&#x1f64a;作者简介&#xff1a;在校研究生&#xff0c;拥有计算机专业的研究生开发团队&#xff0c;分享技术代码帮助学生学习&#xff0c;独立完成自己的网站项目。 代码可以查看文章末尾⬇️联系方式获取&#xff0c;记得注明来意哦~&#x1f339; 赠送计算机毕业设计600…

【大数据学习 | Spark】RDD的概念与Spark任务的执行流程

1. RDD的设计背景 在实际应用中&#xff0c;存在许多迭代式计算&#xff0c;这些应用场景的共同之处是&#xff0c;不同计算阶段之间会重用中间结果&#xff0c;即一个阶段的输出结果会作为下一个阶段的输入。但是&#xff0c;目前的MapReduce框架都是把中间结果写入到HDFS中&…

jmeter操作数据库

简介 Apache JMeter 是一个强大的开源工具&#xff0c;用于负载测试和性能测量。除了Web应用外&#xff0c;JMeter还可以用于测试各种数据库系统&#xff0c;包括MySQL。本文将详细介绍如何使用JMeter来测试MySQL数据库的性能。 环境准备 安装Java&#xff1a;确保你已经安装…

最小生成树——Kruskal、Prim算法

图的存储&#xff1a; 高阶数据结构——图 文章目录 目录 文章目录 一、kruskal算法 二、Prim算法 前言 连通图中的每一棵生成树&#xff0c;都是原图的一个极大无环子图&#xff0c;即&#xff1a;从其中删去任何一条边&#xff0c;生成树 就不在连通&#xff1b;反之&#xf…

STL-stack栈:P1981 [NOIP2013 普及组] 表达式求值

这个题用的STL-栈来做 题目来源&#xff1a;洛谷 相关知识 [NOIP2013 普及组] 表达式求值 题目背景 NOIP2013 普及组 T2 题目描述 给定一个只包含加法和乘法的算术表达式&#xff0c;请你编程计算表达式的值。 输入格式 一行&#xff0c;为需要你计算的表达式&#xff…

数字孪生赋能智慧校园:构建全方位校园安全保障新体系

在11月19日最高人民检察院的党组会上&#xff0c;校园安全问题再次被置于重要议程&#xff0c;会议明确指出&#xff0c;校园安全不仅关乎学生的健康成长&#xff0c;更与社会和谐稳定紧密相连。面对侵害学生权益、危害校园安全的犯罪行为&#xff0c;必须采取“零容忍”态度&a…

Openstack15--块存储服务(Cinder)安装

控制节点 安装Cinder软件包 yum -y install openstack-cinder 安装的“openstack-cinder”软件包里包括“cinder-api”和“cinder-scheduler”模块。安装“openstack-cinder”软件包时&#xff0c;和安装其他OpenStack核心组件时一样&#xff0c;会自动创建名为“cinder”的L…

如何用js方法把页面中的表格导出为excel表格(sheetJS)

目录 一&#xff0c;SheetJS库的基本介绍 这里用到的库是SheetJS&#xff0c;官方文档&#xff1a; sheetJS CE 官方文档 官网对库的解释是&#xff1a; SheetJS社区版提供了经过战斗测试的开源解决方案&#xff0c;用于从几乎任何复杂的电子表格中提取有用的数据&#xf…

自动驾驶系列—告别眩光烦恼:智能大灯如何守护夜间行车安全

&#x1f31f;&#x1f31f; 欢迎来到我的技术小筑&#xff0c;一个专为技术探索者打造的交流空间。在这里&#xff0c;我们不仅分享代码的智慧&#xff0c;还探讨技术的深度与广度。无论您是资深开发者还是技术新手&#xff0c;这里都有一片属于您的天空。让我们在知识的海洋中…

爬虫策略——反爬机制

现代网站通常会使用多种反爬手段来限制爬虫访问数据。了解这些机制并针对性地制定绕过策略&#xff0c;是构建高效爬虫的关键。 1. 常见反爬手段 1.1 User-Agent 检查 网站通常会通过检查请求中的 User-Agent 字段&#xff0c;判断访问是否来自真实用户。爬虫默认的请求库&am…

DataWhale—PumpkinBook(TASK03对数几率回归)

一、课程组成及结构 课程开源地址及相关视频链接&#xff1a;&#xff08;当然这里也希望大家支持一下正版西瓜书和南瓜书图书&#xff0c;支持文睿、秦州等等致力于开源生态建设的大佬✿✿ヽ(▽)ノ✿&#xff09; Datawhale-学用 AI,从此开始 【吃瓜教程】《机器学习公式详解…

系统安全第十三次作业题目及答案

一、 1.计划 实施 检查 处置 2.物理 系统 运行 数据 人员 技术文档 3.物理 网络 系统 应用 管理 二、 1.C 2.B 3.A 4.ACDE 5.ABCD 三、 1. 答&#xff1a; 概念&#xff1a;信息系统安全管理指通过计划、组织、领导、控制等环节来协调人力、物力、财力等资源&#x…

Qml 模型-视图-代理(贰)之 代理(Delegate) 学习

使用模型与视图来定义用户界面时&#xff0c;代理在创建显示时扮演了大量的角色&#xff0c;在模型中的每个元素通过代理来实现可视化。 代理 使用键盘移动 高亮 效果 代码&#xff1a; 视图绑定的属性是 ListView.isCurrentItem: 这个属性是一个布尔值&#xff0c;标识这…

LeetCode 面试经典 150 题回顾

目录 一、数组 / 字符串 1.合并两个有序数组 &#xff08;简单&#xff09; 2.移除元素 &#xff08;简单&#xff09; 3.删除有序数组中的重复项 &#xff08;简单&#xff09; 4.删除有序数组中的重复项 II&#xff08;中等&#xff09; 5.多数元素&#xff08;简单&am…

内外网交换过程中可能遇到的安全风险有哪些?

在数字化时代&#xff0c;企业内外网之间的数据交换变得日益频繁。然而&#xff0c;这一过程中的安全风险和效率问题也日益凸显。我们将探讨内外网交换可能遇到的安全风险&#xff0c;并介绍镭速内外网交换系统如何有效应对这些挑战。 内外网交换过程中的五大安全风险 数据泄露…

人工智能之机器学习概念3【培训机构学习笔记】

定义及作用&#xff1a; 无监督学习是通过试图学习或提取数据背后的数据特征&#xff0c;或者从数据中抽取出重要的特征信息&#xff0c;常见的算法有类聚、降维、文本处理&#xff08;特征抽取&#xff09;等。无监督学习一般是作为有监督学习的前期数据处理&#xff0c;功能…

文件系统的存储方式

磁盘是一个机械设备&#xff0c;外设。 磁盘的基本单位是扇区&#xff0c;一个扇区512字节&#xff0c;4KB。一片可以有n磁道&#xff0c;1磁道可以有m扇区。 如何找到指定位置的扇区&#xff1f;a.找到指定的磁头H b.找到指定的磁道(柱面)C c.找到指定的扇区S。这个叫CHS定址法…

微搭低代码私有化版本升级

目录 1 登录服务器2 进入weda的安装目录3 停止服务4 清除老版本镜像5 下载最新部署包6 重新激活license7 安装服务总结 我们上一篇讲解了部署私有化版本&#xff0c;随着公测的进行&#xff0c;版本是在不断的升级&#xff0c;目前已经到了0.3版本&#xff0c;我们有必要升级一…

JavaSec | JDBC反序列化原理和调用链细节分析

基础知识 JDBC简介 JDBC&#xff08;Java Database Connectivity&#xff0c;Java 数据库连接&#xff09;是 Java 语言中用来规范客户端如何访问数据库的应用程序接口&#xff0c;提供了诸如查询和更新数据在内的方法。JDBC 提供了一种基准&#xff0c;据此可以构建更高级的…

【氮化镓】用于低压射频电源的具有80.4% PAE的Si基E-Mode AlN/GaN HEMT

引言 本文是一篇关于增强型(E-mode)AlN/GaN高电子迁移率晶体管(HEMTs)的研究论文,晶体管是在硅衬底上制造的,并在3.6 GHz频率下展示了80.4%的峰值功率附加效率(PAE)。文章首先介绍了GaN器件在微波和毫米波功率放大器中的应用,特别是在雷达、卫星通信和民用移动通信系…