当前位置: 首页 > news >正文

【LeetCode滑动窗口算法】长度最小的子数组 难度:中等

 我们先看一下题目描述:f0b214303e814dccac0f546fce99a0bc.png

fd0d741ce3f64adc862e4c7df0bfdfc3.png

b72ad29be946429fa2fe0d6e18207610.png

解法一:暴力枚举

时间复杂度:o(n^3)

class Solution {
public:int minSubArrayLen(int target, vector<int>& nums){int i = 0, j = 0;vector<int> v;for (;i < nums.size();i++){int sum = nums[i];for (j = i + 1;j < nums.size();j++){sum = sum + nums[j];if (target == sum){v.push_back(j - i + 1);//j-i+1就是满足条件的子数组的长度break;}}}if (v.empty())return 0;else{sort(v.begin(), v.end());return v[0];}}
};

解法2:利用数组元素的单调性,滑动窗口(同向双指针)算法。

时间复杂度: o(n)

滑动窗口怎么用呢?

1、left=0,right=0

2、进窗口-->判断是否满足条件-->否-->进窗口

                                                      是-->更新结果-->出窗口-->更新结果

滑动窗口算法主要是利用数组元素之和的单调性,规避了很多没有必要的枚举行为。

下面是滑动窗口算法的演示:

bdc828de427d4a3293d884988888e5d0.pngc13020351f3d4829a2d1d7105dc0258a.png

db9663067ee24cf6a431839e0b454276.png 011bae627f5a4ddbb8f8ae530733dd53.png

3ec3649cc64642059686f75ea4c2e7ef.png af4ea62eb82e4383b127f9e36e36a21e.png

下面我们来实现一下基于滑动窗口算法的解题代码:

class Solution {
public:int minSubArrayLen(int target, vector<int>& nums){int sum = 0, len = INT_MAX;for (int left = 0, right = 0;right < nums.size();right++){sum += nums[right];//进入窗口while (sum >= target)//判断{len = min(len, right - left + 1);//更新结果sum -= nums[left++];//出窗口}}return len == INT_MAX ? 0 : len;}
};

相关文章:

【LeetCode滑动窗口算法】长度最小的子数组 难度:中等

我们先看一下题目描述&#xff1a; 解法一&#xff1a;暴力枚举 时间复杂度&#xff1a;o(n^3) class Solution { public:int minSubArrayLen(int target, vector<int>& nums){int i 0, j 0;vector<int> v;for (;i < nums.size();i){int sum nums[i];fo…...

MySQL 用户权限管理:授权、撤销、密码更新和用户删除(图文解析)

目录 前言1. 授予权限2. 撤销权限3. 查询权限4. Demo 前言 公司内部的数据库权限一般针对不同人员有不同的权限分配&#xff0c;而不都统一给一个root权限 1. 授予权限 授予用户权限的基本命令是GRANT 可以授予的权限种类很多&#xff0c;涵盖从数据库和表级别到列和存储过…...

Day39

Day39 JSP JSP底层 全称为Java Server Pages&#xff0c;JSP实际上就是一个servelet JSP:HTML页面Java代码&#xff0c;本质&#xff1a;servlet。 public class login_jsp{//JSP的9大内置对象private JSPWriter out;//当前JSP输出流对象private HttpServletRequest request;…...

Nginx之HTTP模块详解

Nginx是模块化的代码架构&#xff0c;其代码由核心代码与功能模块代码构成。Nginx的主要功能模块是HTTP功能模块&#xff0c;HTTP功能模块在HTTP核心功能的基础上为Nginx对HTTP请求的处理流程提供了扩展功能&#xff0c;这些扩展功能可以让用户很方便地应对访问控制、数据处理、…...

JCR一区 | Matlab实现GAF-PCNN、GASF-CNN、GADF-CNN的多特征输入数据分类预测/故障诊断

JJCR一区 | Matlab实现GAF-PCNN、GASF-CNN、GADF-CNN的多特征输入数据分类预测/故障诊断 目录 JJCR一区 | Matlab实现GAF-PCNN、GASF-CNN、GADF-CNN的多特征输入数据分类预测/故障诊断分类效果格拉姆矩阵图GAF-PCNNGASF-CNNGADF-CNN 基本介绍程序设计参考资料 分类效果 格拉姆…...

最新Prompt预设词分享,DALL-E3文生图+文档分析

使用指南 直接复制使用 可以前往已经添加好Prompt预设的AI系统测试使用&#xff08;可自定义添加使用&#xff09; 支持GPTs SparkAi SparkAi创作系统是基于ChatGPT进行开发的Ai智能问答系统和Midjourney绘画系统&#xff0c;支持OpenAI-GPT全模型国内AI全模型。支持GPT-4o…...

基于SpringBoot+Vue会所产后护理系统设计和实现

基于SpringBootVue会所产后护理系统设计和实现 &#x1f345; 作者主页 网顺技术团队 &#x1f345; 欢迎点赞 &#x1f44d; 收藏 ⭐留言 &#x1f4dd; &#x1f345; 文末获取源码联系方式 &#x1f4dd; &#x1f345; 查看下方微信号获取联系方式 承接各种定制系统 &#…...

Linux中的EINTR和EAGAIN错误码

Linux中的EINTR和EAGAIN错误码 在Linux系统中&#xff0c;进行系统调用时经常会遇到各种错误码。其中&#xff0c;EINTR&#xff08;Interrupted system call&#xff09;和EAGAIN&#xff08;Resource temporarily unavailable&#xff09;是两个较为常见的错误码&#xff0c…...

用户需求分析揭秘:最佳实践与策略

大多数产品团队都有自己处理客户需求的一套流程。但是那些潜在的客户和他们的需求呢&#xff1f;如果在产品管理上已经有一定的资历&#xff0c;很可能对此见惯不怪了。 通常&#xff0c;这些需求是销售人员跑来告诉你的&#xff0c;大概就是说&#xff1a;“超棒的潜在客户一…...

批量创建文件夹 就是这么简单 一招创建1000+文件夹

批量创建文件夹 就是这么简单 一招创建1000文件夹 在工作中&#xff0c;或者生活中&#xff0c;我们经常要用到批量创建文件夹&#xff0c;并且根据不同的工作需求&#xff0c;要求是不一样的&#xff0c;比如有些人需要创建上千个不一样名称的文件夹&#xff0c;如果靠手动创…...

LogicFlow 学习笔记——8. LogicFlow 基础 事件 Event

事件 Event 当我们使用鼠标或其他方式与画布交互时&#xff0c;会触发对应的事件。通过监听这些事件&#xff0c;可以获取其在触发时所产生的数据&#xff0c;根据这些数据来实现需要的功能。详细可监听事件见事件API。 监听事件 lf实例上提供on方法支持监听事件。 lf.on(&…...

Nginx缓存之代理缓存配置

Nginx 的缓存功能是集成在代理模块中的&#xff0c;当启用缓存功能时&#xff0c;Nginx 将请求返回的响应数据持久化在服务器磁盘中&#xff0c;响应数据缓存的相关元数据、有效期及缓存内容等信息将被存储在定义的共享内存中。当收到客户端请求时&#xff0c;Nginx 会在共享内…...

【Android】使用SeekBar控制数据的滚动

项目需求 有一个文本数据比较长&#xff0c;需要在文本右侧加一个SeekBar&#xff0c;然后根据SeekBar的上下滚动来控制文本的滚动。 项目实现 我们使用TextView来显示文本&#xff0c;但是文本比较长的话&#xff0c;需要在TextView外面套一个ScrollView&#xff0c;但是我…...

新能源汽车的能源动脉:中国星坤汽车电缆在新能源汽车电气化中的应用!

随着新能源汽车行业的蓬勃发展&#xff0c;汽车电缆组件作为汽车电气系统的核心组成部分&#xff0c;其重要性日益凸显。中国星坤汽车电缆组件以其卓越的性能和创新技术&#xff0c;为汽车的电能传输、信号传递和控制提供了坚实的保障。本文将深入解析星坤汽车电缆组件的特性、…...

AVL许可证查询系统

在数字化时代&#xff0c;软件已经成为企业运营的核心组成部分。然而&#xff0c;随着软件应用的不断增加&#xff0c;许可证管理也变得越来越复杂。AVL许可证查询系统作为企业软件资产管理的重要工具&#xff0c;能够帮助企业实现对软件许可证的全面掌控。本文将深入探讨AVL许…...

四个步骤,帮你成为价值导向型项目经理

在企业数字化转型的浪潮下&#xff0c;项目管理的方向逐渐从任务导向转变为以价值交付为导向。在快速变化的市场环境中&#xff0c;仅仅关注项目任务的完成已不足以确保项目的成功&#xff0c;需要更加注重项目的最终成果和价值&#xff0c;确保项目能够为组织带来实际的价值和…...

Python3 使用 clickhouse-connect 操作 clickhouse

版本&#xff1a; Python 3.7 x86 clickhouse 24.6.1.3573 clickhouse-connect 0.6.22 代码一&#xff1a; # pip install clickhouse-connectimport clickhouse_connect# 准备参数 host "192.168.1.112" port 8123 username "default" passw…...

Python脚手架系列-DrissionPage

记录DrissionPage模块使用中的一些常常复用的代码,持续更新… 接管谷歌浏览器 from DrissionPage import ChromiumPage, ChromiumOptionsco ChromiumOptions().set_local_port(4249) driver ChromiumPage(addr_or_optsco)创建driver&#xff0c;如果浏览器已开启优先接管&am…...

Java中如何调用mysql中函数

在Java中调用MySQL中的函数&#xff08;无论是存储函数还是自定义函数&#xff09;&#xff0c;通常是通过JDBC&#xff08;Java Database Connectivity&#xff09;来完成的。以下是一个简单的步骤说明和示例代码&#xff0c;展示如何在Java中调用MySQL中的函数。 步骤 添加…...

Huggingface-cli 登录最新版(2024)

安装Huggingface-cli pip install -U "huggingface_hub[cli]"设置好git的邮箱和用户名和huggingface的github账号一致 git config --global user.mail xxx git config --global user.name xxx登录 复制token&#xff0c;划红线的地方&#xff0c;在命令行中点击右…...

华为云AI开发平台ModelArts

华为云ModelArts&#xff1a;重塑AI开发流程的“智能引擎”与“创新加速器”&#xff01; 在人工智能浪潮席卷全球的2025年&#xff0c;企业拥抱AI的意愿空前高涨&#xff0c;但技术门槛高、流程复杂、资源投入巨大的现实&#xff0c;却让许多创新构想止步于实验室。数据科学家…...

装饰模式(Decorator Pattern)重构java邮件发奖系统实战

前言 现在我们有个如下的需求&#xff0c;设计一个邮件发奖的小系统&#xff0c; 需求 1.数据验证 → 2. 敏感信息加密 → 3. 日志记录 → 4. 实际发送邮件 装饰器模式&#xff08;Decorator Pattern&#xff09;允许向一个现有的对象添加新的功能&#xff0c;同时又不改变其…...

7.4.分块查找

一.分块查找的算法思想&#xff1a; 1.实例&#xff1a; 以上述图片的顺序表为例&#xff0c; 该顺序表的数据元素从整体来看是乱序的&#xff0c;但如果把这些数据元素分成一块一块的小区间&#xff0c; 第一个区间[0,1]索引上的数据元素都是小于等于10的&#xff0c; 第二…...

C++初阶-list的底层

目录 1.std::list实现的所有代码 2.list的简单介绍 2.1实现list的类 2.2_list_iterator的实现 2.2.1_list_iterator实现的原因和好处 2.2.2_list_iterator实现 2.3_list_node的实现 2.3.1. 避免递归的模板依赖 2.3.2. 内存布局一致性 2.3.3. 类型安全的替代方案 2.3.…...

大话软工笔记—需求分析概述

需求分析&#xff0c;就是要对需求调研收集到的资料信息逐个地进行拆分、研究&#xff0c;从大量的不确定“需求”中确定出哪些需求最终要转换为确定的“功能需求”。 需求分析的作用非常重要&#xff0c;后续设计的依据主要来自于需求分析的成果&#xff0c;包括: 项目的目的…...

rknn优化教程(二)

文章目录 1. 前述2. 三方库的封装2.1 xrepo中的库2.2 xrepo之外的库2.2.1 opencv2.2.2 rknnrt2.2.3 spdlog 3. rknn_engine库 1. 前述 OK&#xff0c;开始写第二篇的内容了。这篇博客主要能写一下&#xff1a; 如何给一些三方库按照xmake方式进行封装&#xff0c;供调用如何按…...

VB.net复制Ntag213卡写入UID

本示例使用的发卡器&#xff1a;https://item.taobao.com/item.htm?ftt&id615391857885 一、读取旧Ntag卡的UID和数据 Private Sub Button15_Click(sender As Object, e As EventArgs) Handles Button15.Click轻松读卡技术支持:网站:Dim i, j As IntegerDim cardidhex, …...

基于Flask实现的医疗保险欺诈识别监测模型

基于Flask实现的医疗保险欺诈识别监测模型 项目截图 项目简介 社会医疗保险是国家通过立法形式强制实施&#xff0c;由雇主和个人按一定比例缴纳保险费&#xff0c;建立社会医疗保险基金&#xff0c;支付雇员医疗费用的一种医疗保险制度&#xff0c; 它是促进社会文明和进步的…...

工程地质软件市场:发展现状、趋势与策略建议

一、引言 在工程建设领域&#xff0c;准确把握地质条件是确保项目顺利推进和安全运营的关键。工程地质软件作为处理、分析、模拟和展示工程地质数据的重要工具&#xff0c;正发挥着日益重要的作用。它凭借强大的数据处理能力、三维建模功能、空间分析工具和可视化展示手段&…...

如何为服务器生成TLS证书

TLS&#xff08;Transport Layer Security&#xff09;证书是确保网络通信安全的重要手段&#xff0c;它通过加密技术保护传输的数据不被窃听和篡改。在服务器上配置TLS证书&#xff0c;可以使用户通过HTTPS协议安全地访问您的网站。本文将详细介绍如何在服务器上生成一个TLS证…...