每日一题(LeetCode)----数组--长度最小的子数组
每日一题(LeetCode)----数组–长度最小的子数组
1.题目( 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 <= target <= 1091 <= nums.length <= 1051 <= nums[i] <= 105
进阶:
- 如果你已经实现
O(n)时间复杂度的解法, 请尝试设计一个O(n log(n))时间复杂度的解法。
2.解题思路
思路一: 暴力法
暴力法是最直观的方法。初始化子数组的最小长度为无穷大,枚举数组 nums 中的每个下标作为子数组的开始下标,对于每个开始下标 iii,需要找到大于或等于 iii 的最小下标 j,使得从 nums[i] 到 nums[j] 的元素和大于或等于 s,并更新子数组的最小长度(此时子数组的长度是 j−i+1j-i+1j−i+1)。
原作者:力扣官方题解
链接:https://leetcode.cn/problems/backspace-string-compare/
方法二:前缀和 + 二分查找
方法二的时间复杂度是 O(n2),因为在确定每个子数组的开始下标后,找到长度最小的子数组需要 O(n) 的时间。如果使用二分查找,则可以将时间优化到 O(logn)
为了使用二分查找,需要额外创建一个数组 sums 用于存储数组 nums 的前缀和,其中 sums[i]\text{sums}[i]sums[i] 表示从 nums[0] 到 nums[i−1]的元素和。得到前缀和之后,对于每个开始下标 iii,可通过二分查找得到大于或等于 iii 的最小下标 bound,使得 sums[bound]−sums[i−1]≥s,并更新子数组的最小长度(此时子数组的长度是 bound−(i−1))。
因为这道题保证了数组中每个元素都为正,所以前缀和一定是递增的,这一点保证了二分的正确性。如果题目没有说明数组中每个元素都为正,这里就不能使用二分来查找这个位置了。
这里最开始没有看懂,看了力扣上这位网友的评论明白了很多
原作者:力扣官方题解
链接:https://leetcode.cn/problems/backspace-string-compare/

思路三: 滑动窗口
其实滑动窗口就是双指针,我们定义两个指针分别表示滑动窗口的起始位置和结束位置,滑动窗口就是子数组,以此我们就可以求出子数组的总和,看是否符合条件了
初始时滑动窗口的起始位置和结束位置都是数组的首元素,然后我们向右移动滑动窗口的结束位置,相当于是向右遍历一遍数组,每向右移动一位我们都看一下滑动窗口的总和是否大于等于目标值,如果大于我们就计算一下当前子数组长度,然后更新一下答案,之后让滑动窗口的起始位置向后移动一位,直到滑动窗口的总和下于目标值了,我们继续向右遍历,直到遍历结束,得到最终的答案
3.写出代码
思路一的代码:
class Solution {
public:int minSubArrayLen(int s, vector<int>& nums) {int n = nums.size();if (n == 0) {return 0;}int ans = INT_MAX;for (int i = 0; i < n; i++) {int sum = 0;for (int j = i; j < n; j++) {sum += nums[j];if (sum >= s) {ans = min(ans, j - i + 1);break;}}}return ans == INT_MAX ? 0 : ans;}
};
原作者:力扣官方题解
链接:https://leetcode.cn/problems/backspace-string-compare/
思路二的代码:
class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int length=nums.size();vector<int> sum(length+1,0);int ans=0x7fffffff;//得到前缀和for(int i=1;i<=length;i++){sum[i]=sum[i-1]+nums[i-1];}//遍历得到答案for(int i=1;i<=length;i++){int temp=target+sum[i-1];int bound=lower_bound(sum.begin(),sum.end(),temp)-sum.begin();//注意:lower_bound函数的返回值是第一个大于等于目标值的地址,所以我们这里减去首元素的地址就可以获得第一个大于等于目标值的下标了if(bound<length+1){ans=min(ans,bound-(i-1));}}if(ans==0x7fffffff){return 0;}else{return ans;}}
};
思路三的代码:
class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int length=nums.size();int i=0;int sum=0;int result=0x7fffffff;for(int j=0;j<length;j++){sum+=nums[j];while(sum>=target){result=min(result,j-i+1);sum-=nums[i];i++;}}if(result==0x7fffffff){return 0;}else{return result;}}
};
相关文章:
每日一题(LeetCode)----数组--长度最小的子数组
每日一题(LeetCode)----数组–长度最小的子数组 1.题目( 209.长度最小的子数组) 给定一个含有 n 个正整数的数组和一个正整数 target 。 找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组 [numsl, numsl1, ..., numsr-1, numsr] &…...
TCP与UDP
文章目录 TCP与UDP传输层的作用端口号UDPTCPUDP首部的格式TCP首部格式 TCP与UDP TCP/IP中有两个具有代表性的传输层协议,它们分别是TCP和UDP。TCP提供可靠的通信传输,而UDP则常被用于让广播和细节控制交给应用的通信传输。总之,根据通信的具…...
js实现对象数组去重
数组去重,一般会在面试的时候才会碰到,要求手写数组去重方法的代码。如果是被提问到,数组去重的方法有哪些?你能答出其中的10种,面试官很有可能对你刮目相看。 在实际项目中碰到的数组去重,一般都是后台去处…...
2023 极术通讯-安谋科技发布“山海”S20F安全解决方案,持续加码智能汽车“芯”赛道
导读:极术社区推出极术通讯,引入行业媒体和技术社区、咨询机构优质内容,定期分享产业技术趋势与市场应用热点。 芯方向 AMBA向多芯片和CHI C2C进发 Arm的Advanced Microcontroller Bus Architecture(AMBA)在与生态系…...
GRPC学习
GRPC元数据 在gRPC中,元数据(metadata)是用于在gRPC请求和响应中传递附加信息的一种机制。元数据是以键值对(key-value pairs)的形式组织的信息,它可以包含请求的上下文信息、安全凭证、消息传输相关的信息…...
c++ latch 使用详解
c latch 使用详解 std::latch c20 头文件 #include <latch>。作用:提供了一种机制,可以让一个或多个线程等待,直到计数器减为零。注意事项: latch 为向下计数器,即只能减少不能增加或者重置。这也使得其只能单…...
linux 下正确使用cp命令复制目录
linux下复制目录时,cp -r 没有 cp -a 好: 使用cp -r 拷贝数据,拷贝的结果是生成新的时间戳等信息 使用cp -a 相当于将原数据原封不动的拷贝过来,不改变里面的任何信息 指定目录时, 源目录/* 【说明:斜…...
CTF----Web真零基础入门
目录 前置知识导图: TCP/IP体系结构(IP和端口): IP是什么:是计算机在互联网上的唯一标识(坐标,代号),用于在互联网中寻找计算机。 内网(局域网…...
css实现元素四周阴影
前言 首先确定的是需要使用box-shadow这一属性 语法如下: box-shadow: h-shadow v-shadow blur spread color inset; h-shadow:表示水平方向上的阴影偏移量,必须指明,可以是正数、负数、0,如果为正数左方有阴影&…...
《QT从基础到进阶·二十五》界面假死处理
假如有这样一种情况,我们在主线程写了一个死循环,当程序运行到主线程的死循环代码后界面便卡死点了没有反应,这里提供几种方法处理界面假死的情况,保证比如主线程在执行死循环没有退出的时候点击界面不会卡死能继续执行其他功能。…...
卷积神经网络(1)
目录 卷积 1 自定义二维卷积算子 2 自定义带步长和零填充的二维卷积算子 3 实现图像边缘检测 4 自定义卷积层算子和汇聚层算子 4.1 卷积算子 4.2 汇聚层算子 5 学习torch.nn.Conv2d()、torch.nn.MaxPool2d();torch.nn.avg_pool2d(),简要介绍使用方…...
Mysql中名叫infomaiton_schema的数据库是什么东西?
在 MySQL 中,information_schema 是一个系统数据库,用于存储关于数据库服务器元数据的信息。它并不存储用户数据,而是包含有关数据库、表、列、索引、权限等方面的元数据信息。这些信息可以通过 SQL 查询来获取,用于了解和管理数据…...
Django(复习篇)
项目创建 1. 虚拟环境 python -m venv my_env cd my_env activate/deactivate pip install django 2. 项目和app创建 cd mypros django-admin startproject Pro1 django-admin startapp app1 3. settings配置INSTALLED_APPS【app1"】TEMPLATES【 DIRS: [os.pat…...
MySQL里对时间的加减操作及常用语法
查询当前时间: select NOW(); //2023-11-14 11:36:03 select CURDATE(); //2023-11-14 SELECT CURTIME(); //11:36:03日期加日期: select date_add(NOW(), interval 1 year); //加1年 select date_add(NOW(), interval 1 month); …...
『MySQL快速上手』-⑨-复合查询
文章目录 1.基本查询回顾2.多表查询案例3.自链接案例4.子查询4.1 单行子查询4.2 多行子查询4.3 多列子查询4.4 在from子句中使用子查询5.合并查询5.1 union5.2 union all6.表的内连和外连6.1 内连接6.2 外连接6.2.1 左外连接6.2.2 右外连接...
高并发架构设计(三大利器:缓存、限流和降级)
引言 高并发背景 互联网行业迅速发展,用户量剧增,系统面临巨大的并发请求压力。 软件系统有三个追求:高性能、高并发、高可用,俗称三高。三者既有区别也有联系,门门道道很多,全面讨论需要三天三夜&#…...
ElasticSearch7.x - HTTP 操作 - 文档操作
创建文档(添加数据) 索引已经创建好了,接下来我们来创建文档,并添加数据。这里的文档可以类比为关系型数 据库中的表数据,添加的数据格式为 JSON 格式 向 ES 服务器发 POST 请求 :http://192.168.254.101:9200/shopping/_doc 请求体内容为: {"title":"小…...
[数据结构大作业]HBU 河北大学校园导航
校园导航实验报告 问题描述: 以我校为例,设计一个校园导航系统,主要为来访的客人提供信息查询。系统有两类登陆账号,一类是游客,使用该系统方便校内路线查询;一类是管理员,可以使用该系统查询…...
立体库堆垛机控制程序手动功能实现
手动操作功能模块 手动前后保护锁 *************提升手动程序段 手动上升,下降保护锁 **********货叉手动程序段...
git commit提交报错
git commit -m 名字’时报一下错误: [FAILED] npm run lint-staged:js [FAILED] [FAILED] npm run lint-staged:js [FAILED] [SUCCESS] Running tasks for staged files..npm ERR! code EPERM npm ERR! syscall open npm ERR! path C:\Program Files\nodejs\node_c…...
Python|GIF 解析与构建(5):手搓截屏和帧率控制
目录 Python|GIF 解析与构建(5):手搓截屏和帧率控制 一、引言 二、技术实现:手搓截屏模块 2.1 核心原理 2.2 代码解析:ScreenshotData类 2.2.1 截图函数:capture_screen 三、技术实现&…...
Linux 文件类型,目录与路径,文件与目录管理
文件类型 后面的字符表示文件类型标志 普通文件:-(纯文本文件,二进制文件,数据格式文件) 如文本文件、图片、程序文件等。 目录文件:d(directory) 用来存放其他文件或子目录。 设备…...
Robots.txt 文件
什么是robots.txt? robots.txt 是一个位于网站根目录下的文本文件(如:https://example.com/robots.txt),它用于指导网络爬虫(如搜索引擎的蜘蛛程序)如何抓取该网站的内容。这个文件遵循 Robots…...
让AI看见世界:MCP协议与服务器的工作原理
让AI看见世界:MCP协议与服务器的工作原理 MCP(Model Context Protocol)是一种创新的通信协议,旨在让大型语言模型能够安全、高效地与外部资源进行交互。在AI技术快速发展的今天,MCP正成为连接AI与现实世界的重要桥梁。…...
【论文阅读28】-CNN-BiLSTM-Attention-(2024)
本文把滑坡位移序列拆开、筛优质因子,再用 CNN-BiLSTM-Attention 来动态预测每个子序列,最后重构出总位移,预测效果超越传统模型。 文章目录 1 引言2 方法2.1 位移时间序列加性模型2.2 变分模态分解 (VMD) 具体步骤2.3.1 样本熵(S…...
Java多线程实现之Thread类深度解析
Java多线程实现之Thread类深度解析 一、多线程基础概念1.1 什么是线程1.2 多线程的优势1.3 Java多线程模型 二、Thread类的基本结构与构造函数2.1 Thread类的继承关系2.2 构造函数 三、创建和启动线程3.1 继承Thread类创建线程3.2 实现Runnable接口创建线程 四、Thread类的核心…...
在web-view 加载的本地及远程HTML中调用uniapp的API及网页和vue页面是如何通讯的?
uni-app 中 Web-view 与 Vue 页面的通讯机制详解 一、Web-view 简介 Web-view 是 uni-app 提供的一个重要组件,用于在原生应用中加载 HTML 页面: 支持加载本地 HTML 文件支持加载远程 HTML 页面实现 Web 与原生的双向通讯可用于嵌入第三方网页或 H5 应…...
Java编程之桥接模式
定义 桥接模式(Bridge Pattern)属于结构型设计模式,它的核心意图是将抽象部分与实现部分分离,使它们可以独立地变化。这种模式通过组合关系来替代继承关系,从而降低了抽象和实现这两个可变维度之间的耦合度。 用例子…...
c# 局部函数 定义、功能与示例
C# 局部函数:定义、功能与示例 1. 定义与功能 局部函数(Local Function)是嵌套在另一个方法内部的私有方法,仅在包含它的方法内可见。 • 作用:封装仅用于当前方法的逻辑,避免污染类作用域,提升…...
深度剖析 DeepSeek 开源模型部署与应用:策略、权衡与未来走向
在人工智能技术呈指数级发展的当下,大模型已然成为推动各行业变革的核心驱动力。DeepSeek 开源模型以其卓越的性能和灵活的开源特性,吸引了众多企业与开发者的目光。如何高效且合理地部署与运用 DeepSeek 模型,成为释放其巨大潜力的关键所在&…...
