[数组二分查找] 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.rhkb.cn/news/474906.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Java从入门到精通笔记篇(十三)

与流处理 ambda表达式 定义 lambda表达式不能被独立执行&#xff0c;因此必须实现函数式接口&#xff0c;并且会返回一个函数式接口的对象。 可将其语法用下列的方式理解 误区警示 “->”符号是由英文状态下的“-”和“>”组成的&#xff0c;符号之间没有空格。 lambd…

kvm-dmesg:从宿主机窥探虚拟机内核dmesg日志

在虚拟化环境中&#xff0c;实时获取虚拟机内核日志对于系统管理员和开发者来说至关重要。传统的 dmesg 工具可以方便地查看本地系统的内核日志&#xff0c;但在KVM&#xff08;基于内核的虚拟机&#xff09;环境下&#xff0c;获取虚拟机内部的内核日志则复杂得多。为了简化这…

apipost下载安装教程、脚本详细使用教程

目录 apipost脚本使用教程 缘由&#xff1a; 实现流程&#xff1a; 1、设置接口需要的URL&#xff1a; 2、boby: 3、预执行操作&#xff1a; 4、断言 5、执行结果&#xff1a; 什么是ApiPost&#xff1f; 下载以及安装&#xff1a; apipost使用文档介绍&#xff1a;…

25. 架构能力

文章目录 第25章 架构能力25.1 个人能力&#xff1a;架构师的职责、技能和知识职责技能知识那经验方面呢&#xff1f; 25.2 软件架构组织的能力25.3 成为更优秀的架构师接受指导指导他人 25.4 小结25.5 扩展阅读25.6 问题讨论 第25章 架构能力 人生苦短&#xff0c;学海无涯。 …

UniApp的Vue3版本中H5配置代理的最佳方法

UniApp的Vue3版本中H5项目在本地开发时需要配置跨域请求调试 最开始在 manifest.json中配置 总是报404&#xff0c;无法通过代理请求远程的接口并返回404错误。 经过验证在项目根目录创建 vite.config.js文件 vite.config.js内容: // vite.config.js import {defineConfig }…

kafka基础

文章目录 一、Kafka入门1.1、JMS1.2、生产者-消费者模式1.3、ZooKeeper 二、kafka基础架构2.1、producer2.2、kafka cluster2.2.1、broker2.2.2、Controller2.2.3、Topic2.2.4、Partition2.2.5、Replication2.2.6、Leader & Follower 2.3、consumer 一、Kafka入门 Kafka是一…

SIMCom芯讯通A7680C在线升级:FTP升级成功;http升级腾讯云对象储存的文件失败;http升级私有服务器的文件成功

从事嵌入式单片机的工作算是符合我个人兴趣爱好的,当面对一个新的芯片我即想把芯片尽快搞懂完成项目赚钱,也想着能够把自己遇到的坑和注意事项记录下来,即方便自己后面查阅也可以分享给大家,这是一种冲动,但是这个或许并不是原厂希望的,尽管这样有可能会牺牲一些时间也有哪天原…

CSS一些练习过程

1.字体样式 代码&#xff1a; <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0"><title>Document</title…

Linux系统Centos设置开机默认root用户

目录 一. 教程 二. 部分第三方工具配置也无效 一. 教程 使用 Linux 安装Centos系统的小伙伴大概都知道&#xff0c;我们进入系统后&#xff0c;通常都是自己设置的普通用户身份&#xff0c;而不是 root 超级管理员用户&#xff0c;导致我们在操作文件夹时往往爆出没有权限&am…

【机器学习】机器学习中用到的高等数学知识-7.信息论 (Information Theory)

熵 (Entropy)&#xff1a;用于评估信息的随机性&#xff0c;常用于决策树和聚类算法。交叉熵 (Cross-Entropy)&#xff1a;用于衡量两个概率分布之间的差异&#xff0c;在分类问题中常用。 信息论作为处理信息量和信息传输的数学理论&#xff0c;在机器学习中具有广泛的应用。…

【C#】C#编程入门指南:构建你的.NET开发基础

文章目录 前言&#xff1a;1. C# 开发环境 VS的基本熟悉2. 解决方案与项目的关系3. 编辑、编译、链接、运行4. 托管代码和CLR4.1 CLR&#xff1a;4.2 C# 代码第编译过程&#xff08;两次编译的&#xff09; 5. 命名空间6. 类的组成与分析7. C# 的数据类型7.1 值类型7.2 引用类型…

手摸手5-springboot开启打印sql完整语句

目录 手摸手5-springboot开启打印sql完整语句简介 p6spy简介引入依赖修改application-jdbc.yaml配置配置spy.properties文件配置项运行后效果 手摸手5-springboot开启打印sql完整语句 简介 MyBatis-Plus提供了SQL分析与打印的功能&#xff0c;通过集成p6spy组件&#xff0c;可…

深入解析TK技术下视频音频不同步的成因与解决方案

随着互联网和数字视频技术的飞速发展&#xff0c;音视频同步问题逐渐成为网络视频播放、直播、编辑等过程中不可忽视的技术难题。尤其是在采用TK&#xff08;Transmission Keying&#xff09;技术进行视频传输时&#xff0c;由于其特殊的时序同步要求&#xff0c;音视频不同步现…

力扣(leetcode)题目总结——动态规划篇

leetcode 经典题分类 链表数组字符串哈希表二分法双指针滑动窗口递归/回溯动态规划二叉树辅助栈 本系列专栏&#xff1a;点击进入 leetcode题目分类 关注走一波 前言&#xff1a;本系列文章初衷是为了按类别整理出力扣&#xff08;leetcode&#xff09;最经典题目&#xff0c…

MySQL超详细安装配置教程(亲测有效)

目录 1.下载mysql 2.环境配置 3.安装mysql ​4.navicat工具下载与连接 ​5总结 1.下载mysql mysql下载--MySQL &#xff1a;&#xff1a; 下载 MySQL 社区服务器 下载的时候这里直接逃过就行 我这里的版本是最新的mysql8.0.37 下载完成之后,将压缩包进行解压 这里我建议大…

高阶云服务-ELB+AS

ELBAS 弹性负载均衡弹性伸缩 原来1台web服务器不满足相应&#xff0c;现部署多台提供相同服务&#xff1b; 由于多个服务器多个ip该如何提供给应用呢&#xff1f; 引申出负载均衡&#xff08;HAProxy&#xff0c;LVS01四层&#xff0c;Nginx七层&#xff09; 防单点故障做主备…

python蓝桥杯刷题2

1.最短路 题解&#xff1a;这个采用暴力枚举&#xff0c;自己数一下就好了 2.门牌制作 题解&#xff1a;门牌号从1到2020&#xff0c;使用for循环遍历一遍&#xff0c;因为range函数无法调用最后一个数字&#xff0c;所以设置成1到2021即可&#xff0c;然后每一次for循环&…

阿里云轻量应用服务器可以用在哪些场景呢

在数字化转型的浪潮中&#xff0c;中小企业面临着如何快速、高效地上云的挑战。阿里云轻量应用服务器&#xff08;SWAS&#xff09;作为一款专为中小企业设计的云服务产品&#xff0c;提供了简单易用、经济实惠的解决方案&#xff0c;助力企业轻松实现云端部署&#xff0c;赋能…

git合并分支

首先是UI非常建议切换成传统的UI&#xff1a; 当前所在分支email 右键切换的时候chekout 点击之后就可以切换了 再执行查看就知道已经切换到了main分支&#xff1b; 总结&#xff1a; git branch 查看当前分支&#xff0c;其实不用查看你看或者小图标&#xff0c;就是那…

《生成式 AI》课程 第3講 CODE TASK执行文章摘要的机器人

课程 《生成式 AI》课程 第3講&#xff1a;訓練不了人工智慧嗎&#xff1f;你可以訓練你自己-CSDN博客 任务1:总结 1.我们希望你创建一个可以执行文章摘要的机器人。 2.设计一个提示符&#xff0c;使语言模型能够对文章进行总结。 model: gpt-4o-mini,#gpt-3.5-turbo, import…