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

ops/2024/11/20 23:14:12/

文章目录

      • 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.ppmy.cn/ops/135350.html

相关文章

windows C#-编写 C# LINQ 查询(上)

介绍性的语言集成查询 (LINQ) 文档中的大多数查询是使用 LINQ 声明性查询语法编写的。 但是在编译代码时&#xff0c;查询语法必须转换为针对 .NET 公共语言运行时 (CLR) 的方法调用。 这些方法调用会调用标准查询运算符(名称为 Where、Select、GroupBy、Join、Max 和 Average …

Python绘制雪花

文章目录 系列目录写在前面技术需求完整代码代码分析1. 代码初始化部分分析2. 雪花绘制核心逻辑分析3. 窗口保持部分分析4. 美学与几何特点总结 写在后面 系列目录 序号直达链接爱心系列1Python制作一个无法拒绝的表白界面2Python满屏飘字表白代码3Python无限弹窗满屏表白代码4…

199. 二叉树的右视图【 力扣(LeetCode) 】

文章目录 零、原题链接一、题目描述二、测试用例三、解题思路四、参考代码 零、原题链接 199. 二叉树的右视图 一、题目描述 给定一个二叉树的 根节点 root&#xff0c;想象自己站在它的右侧&#xff0c;按照从顶部到底部的顺序&#xff0c;返回从右侧所能看到的节点值。 二…

Node.js 版本管理的最终答案 Volta

文章目录 特点安装Unix系统安装Windows系统安装 常用命令volta fetchvolta installvolta uninstallvolta pinvolta listvolta completionsvolta whichvolta setupvolta runvolta help 建议 目前对于前端项目的node 版本&#xff0c;我们一般会在项目 package.json 的 engines 字…

lua调用C语言函数,在函数中进行类型检查

使用lua_is*函数族进行检查&#xff08;除了lua_type之外的另一种方式&#xff09; Lua C API提供了一系列lua_is*函数&#xff0c;如lua_isnumber、lua_isstring、lua_isboolean等&#xff0c;用于检查栈上元素的类型。示例代码如下&#xff0c;假设我们有一个C函数&#xff0…

Deep-Live-Cam -面部交换、视频深度伪造

文章目录 一、关于 Deep-Live-Cam免责声明 二、安装&#xff08;Windows/Nvidia&#xff09;安装&#xff08;手动&#xff09;基本安装&#xff08;CPU&#xff09; GPU加速&#xff08;可选&#xff09;CUDA执行提供商&#xff08;Nvidia&#xff09;CoreML执行提供商&#x…

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

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

Java 设计模式 详解

在Java开发中&#xff0c;设计模式是一种常见的、成熟的解决方案&#xff0c;用于应对特定的设计问题和复杂性管理。以下是一些常用的设计模式&#xff0c;它们可以分为三类&#xff1a;创建型模式、结构型模式和行为型模式。 一、创建型模式 创建型模式主要负责对象的创建&a…