( 数组) 209. 长度最小的子数组——【Leetcode每日一题】

news/2024/10/9 12:35:29/

❓209. 长度最小的子数组

难度:中等

给定一个含有 n 个正整数的数组和一个正整数 target

找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ,并返回其长度。如果不存在符合条件的子数组,返回 0

示例 1:

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

示例 2:

输入:target = 4, nums = [1,4,4]
输出:1

示例 3:

输入:target = 11, nums = [1,1,1,1,1,1,1,1]
输出:0

提示:

  • 1 < = t a r g e t < = 1 0 9 1 <= target <= 10^9 1<=target<=109
  • 1 < = n u m s . l e n g t h < = 1 0 5 1 <= nums.length <= 10^5 1<=nums.length<=105
  • 1 < = n u m s [ i ] < = 1 0 5 1 <= nums[i] <= 10^5 1<=nums[i]<=105

进阶:

如果你已经实现 O(n) 时间复杂度的解法, 请尝试设计一个 O(nlog(n)) 时间复杂度的解法。

💡思路:滑动窗口

定义两个指针 ij 分别表示子数组(滑动窗口窗口)的开始位置结束位置,维护变量 sum 存储子数组中的元素和(即从 nums[i]nums[j] 的元素和)。

初始状态下, ij 都指向下标 0sum 的值为 0:

  • 每一轮迭代,将 nums[j] 加到 sum,如果 sum ≥ target,则更新子数组的最小长度(此时子数组的长度是 j − i + 1
  • 然后将 nums[i]sum 中减去并将 i 右移,直到 sum < target,在此过程中同样更新子数组的最小长度。
  • 在每一轮迭代的最后,将 j 右移。

在这里插入图片描述

🍁代码:(Java、C++)

Java

class Solution {public int minSubArrayLen(int target, int[] nums) {int i = 0; // 滑动窗口起始位置int sum = 0; // 滑动窗口数值之和int ans = Integer.MAX_VALUE;for(int j = 0; j < nums.length; j++){sum += nums[j];//窗口内所有数的和while(sum >= target) {//窗口内所有数的和大于target,则前移i(起始位置)ans = ans < j - i + 1 ? ans : j - i + 1;sum -= nums[i++];// 这里体现出滑动窗口的精髓之处,不断变更i(子序列的起始位置)}}return ans == Integer.MAX_VALUE ? 0 : ans;}
}

C++

class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int i = 0; // 滑动窗口起始位置int sum = 0; // 滑动窗口数值之和int ans = INT_MAX;for(int j = 0; j < nums.size(); j++){sum += nums[j];//窗口内所有数的和while(sum >= target) {//窗口内所有数的和大于target,则前移i(起始位置)ans = ans < j - i + 1 ? ans : j - i + 1;sum -= nums[i++];// 这里体现出滑动窗口的精髓之处,不断变更i(子序列的起始位置)}}return ans == INT_MAX ? 0 : ans;}
};

🚀 运行结果:

在这里插入图片描述

🕔 复杂度分析:

  • 时间复杂度 O ( n ) O(n) O(n),其中 n 为数组的长度。
  • 空间复杂度 O ( 1 ) O(1) O(1)

题目来源:力扣。

放弃一件事很容易,每天能坚持一件事一定很酷,一起每日一题吧!
关注我LeetCode主页 / CSDN—力扣专栏,每日更新!

注: 如有不足,欢迎指正!


http://www.ppmy.cn/news/77754.html

相关文章

软考 软件设计师计算机网络笔记

网络设备 物理层的互联设备有中继器和集线器&#xff0c;集线器是一种特殊的多路多端口中继器 数据链路层的互连设备有网桥&#xff0c;交换机&#xff0c;交换机是一个多端口的网桥 网络层互连设备有路由器 协议簇 所有带T的除了TFTP其他都是TCP&#xff0c;所有不带T的除…

方案绞尽脑汁想不出?试试这款AI代写方案

一份计划方案&#xff0c;往往是工作进行下去的核心环节&#xff0c;需要考虑很多因素和变量&#xff0c;在某些情况下&#xff0c;可能没有足够的信息来制定有效的方案。这可能会导致需要额外的研究和调查&#xff0c;以便了解更多关于问题的信息&#xff0c;这将延长制定方案…

说说 HWND_TOP 和 HWND_TOPMOST 的区别

初看上去&#xff0c;HWND_TOP 和 HWND_TOPMOST 有点类似&#xff0c;但是实际上在调用 DeferWindowPos 或者 SetWindowPos时&#xff0c;它们之间的差别还挺大。 在同级窗口的维护机制中&#xff0c;有一个概念叫做 Z 序 (Z-order) 。出于此讨论的目的&#xff0c;顶级窗口也…

卷麻了,公司新来的00后测试用例写的比我还好,简直无地自容......

经常看到无论是刚入职场的新人&#xff0c;还是工作了一段时间的老人&#xff0c;都会对编写测试用例感到困扰&#xff1f;例如&#xff1a; 如何编写测试用例&#xff1f; 作为一个测试新人&#xff0c;刚开始接触测试&#xff0c;对于怎么写测试用例很是头疼&#xff0c;无法…

DOS的常用指令:

DOS的常用指令&#xff1a; DOS【介绍】&#xff1a;磁盘操作系统 cmd是操作DOS的媒介&#xff0c;dos可以操作Windows的目录结构&#xff0c; 基本操作指令&#xff1a; cmd【控制台】->发给dos【解析】->win的目录结构 常用操作指令&#xff1a; 《一》目录操作 &a…

关注 | 蛙色元宇宙,正式成为XRMA联盟成员单位

中国虚拟现实与元宇宙产业峰会&#xff0c;2023年3月22日于杭州圆满结束&#xff0c;在杭州市人民政府、浙江省经济和信息化厅指导&#xff0c;由杭州市经济和信息化局、杭州市西湖区人民政府主办&#xff0c;中国信息通信研究院承办。 蛙色元宇宙作为元宇宙的领先企业之一&…

边缘人工智能——nanodet模型实践指引,从标注数据集到实现部署文件

内容概述 首先获得一个合适的nanodet模型版本&#xff0c;配置nanodet适用的环境&#xff0c;然后对网上公开的生数据集进行重新标注&#xff0c;配置nanodet并进行训练&#xff0c;.pth到.onnx的模型转化及简化&#xff0c;编写推理文件。 文章着重于实践方向指引&#xff0c;…

golang-mysql、sqlx

1.导包 go get -u github.com/go-sql-driver/mysql import _ "github.com/go-sql-driver/mysql"_ 表示只执行包中init函数&#xff0c;mysql包会在init函数中注册自己。 2.连接数据库 利用基本库database/sql连接数据库 dsn : "root:123456tcp(127.0.0.1:330…