【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;}
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/348936.html

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

相关文章

CLIP-guided Prototype Modulating for Few-shot Action Recognition

标题&#xff1a;基于CLIP引导的原型调制用于少样本动作识别 源文链接&#xff1a;CLIP-guided Prototype Modulating for Few-shot Action Recognition | International Journal of Computer Vision (springer.com)https://link.springer.com/article/10.1007/s11263-023-019…

wireshark查看流量图

点击 菜单中的 统计 , 选择 IO 图表 项 勾选下面选项..

java.nio.charset.UnmappableCharacterException

问题 java.lang.IllegalArgumentException: java.nio.charset.UnmappableCharacterException: Input length 1 解释为编码转换有问题 问题错在位置 非汉字存在 打包的时候就会报异常

Vue基本使用-02

上节我们讲了什么是mvvm模型&#xff0c;以及我们vue的一些常用指令&#xff0c;今天给大家讲一下vue的基本使用&#xff0c;在将之前我们需要重点讲解我们的一个指令&#xff0c;v-model指令 v-model v-model 可以在组件上使用以实现双向绑定,什么是双向绑定呢?意思就是当我们…

2024年第三届数据统计与分析竞赛(B题)数学建模完整思路+完整代码全解全析

你是否在寻找数学建模比赛的突破点&#xff1f;数学建模进阶思路&#xff01; 详细请查 作为经验丰富的数学建模团队&#xff0c;我们将为你带来2024年第三届数据统计与分析竞赛&#xff08;B题&#xff09;的全面解析。这个解决方案包不仅包括完整的代码实现&#xff0c;还有…

分享一份 .NET Core 简单的自带日志系统配置,平时做一些测试或个人代码研究,用它就可以了

前言 实际上&#xff0c;.NET Core 内部也内置了一套日志系统&#xff0c;它是一个轻量级的日志框架&#xff0c;用于记录应用程序的日志信息。 它提供了 ILogger 接口和 ILoggerProvider 接口&#xff0c;以及一组内置的日志提供程序&#xff08;如 Console、Debug、EventSo…

Python学习从0开始——Kaggle时间序列002

Python学习从0开始——Kaggle时间序列002 一、作为特征的时间序列1.串行依赖周期 2.滞后序列和滞后图滞后图选择滞后 3.示例 二、混合模型1.介绍2.组件和残差3.残差混合预测4.设计混合模型5.使用 三、使用机器学习进行预测1.定义预测任务2.为预测准备数据3.多步骤预测策略3.1 M…

docker 部署nginx多级子域名(三级四级...)映射不同web项目,访问不同路径地址

一、背景 只有一台服务器&#xff0c;一个顶级域名&#xff0c;现在需要根据不同子域名访问不同web项目&#xff0c;比如 # 管理后台 cms.biacu.com# 客户端h5 h5.biacu.com# 四级域名 h5.s.biacu.com同时&#xff0c;不同web项目放在不同位置 二、 1、在云服务器上&#x…

C++——计算不同的非空子串个数

计算不同的非空子串 计算方法 这道题是我在BCSP-X小高组的题目中发现的一道 没事闲的就写了代码和思路&#xff1a; 代码 #include <iostream> #include <vector> #include <string> #include <algorithm>using namespace std;// 用于存储后缀数…

AnythingLLM 的 Docker 使用

AnythingLLM是使用大语言模型LLM的一站式简便框架。官网的介绍如下&#xff1a; AnythingLLM is the easiest to use, all-in-one AI application that can do RAG, AI Agents, and much more with no code or infrastructure headaches. 1. 使用官方docker 最方便的方法是使…

IDEA项目上传Github流程+常见问题解决

一、Github上创建仓库 项目创建好后如图所示 二、IDEA连接Github远程仓库 管理远程 复制远程地址 定义远程 登录Github 点击进入File->Settings->Version Control->Github登录自己的账号并勾上“√” 三、推送项目 点击推送 修改为main 点击确定&#xff0c;打开远程…

【智能算法应用】基于粒子群算法的多尺度Retinex图像去雾方法

目录 1.算法原理2.粒子群算法的多尺度Retinex图像去雾方法3.结果展示4.参考文献5.代码获取 1.算法原理 【智能算法】粒子群算法&#xff08;PSO&#xff09;原理及实现 多尺度Retinex算法 在Retinex算法中&#xff0c;雾化图像的形成可以总结为入射光和反射光的乘积: I ( x…

【算法训练记录——Day28】

Day28——回溯算法Ⅳ 1.复原IP地址2.[全排列](https://leetcode.cn/problems/permutations/submissions/539240290/)3.[全排列Ⅱ](https://leetcode.cn/problems/permutations-ii/description/) ● 93.复原IP地址 ● 78.子集 ● 90.子集II 1.复原IP地址 思路&#xff1a;相当于…

SSM情侣购物系统 -计算机毕业设计源码02387

目 录 摘要 1 绪论 1.1 开发背景与意义 1.2开发意义 1.3Vue.js 主要功能 1.3论文结构与章节安排 2 情侣购物系统系统分析 2.1 可行性分析 2.2 系统流程分析 2.2.1 数据流程 3.3.2 业务流程 2.3 系统功能分析 2.3.1 功能性分析 2.3.2 非功能性分析 2.4 系统用例分…

细说MCU串口函数及使用printf函数实现串口发送数据的方法

目录 1、硬件及工程 2、串口相关的库函数 &#xff08;1&#xff09;串口中断服务函数&#xff1a; &#xff08;2&#xff09;串口接收回调函数&#xff1a; &#xff08;3&#xff09;串口接收中断配置函数&#xff1a; &#xff08;4&#xff09;非中断发送&#xff…

[linux]如何跟踪linux 内核运行的流程呢

前面已经可以把内核编译出来&#xff0c;但是作为技术狗想看到内核是怎么运行的怎么办&#xff1f; 内核很多代码都是C语言写的&#xff0c;那简单&#xff0c;添加2行代码&#xff1a; include/linux/printk.h 529和530原来的&#xff1a; #define pr_info(fmt, ...) \ …

IIoT(智能物联网)的现状、应用及安全

近年来&#xff0c;物联网&#xff08;IoT&#xff09;作为推动现代公司和智能城市发展的一个范式&#xff0c;已经取得了显著的发展。IoT使得分布式设备&#xff08;如手机、平板电脑和计算机&#xff09;能够感知并从外部环境传输数据&#xff0c;以服务于最终用户。IoT的概念…

TcpClient 服务器、客户端连接

TcpClient 服务器 TcpListener 搭建tcp服务器的类&#xff0c;基于socket套接字通信的 1 创建服务器对象 TcpListener server new TcpListener(IPAddress.Parse("127.0.0.1"), 3000); 2 开启服务器 设置最大连接数 server.Start(1000); 3 接收客户端的链接,只能…

华为昇腾异构计算架构CANN及AI芯片简介

异构计算架构CANN 异构计算架构CANN&#xff08;Compute Architecture for Neural Networks&#xff09;是华为针对AI场景推出的异构计算架构&#xff0c;向上支持多种AI框架&#xff0c;包括MindSpore、PyTorch、TensorFlow等&#xff0c;向下服务AI处理器与编程&#xff0c;…

Open vSwitch 中 upcall 消息的类型

一、upcall 调用的流程 在 Open vSwitch 的数据包转发流程中&#xff0c;如果数据包在内核空间无法完全处理&#xff08;比如匹配不到流表项&#xff09;&#xff0c;就会发生 upcall 调用&#xff0c;将数据包从内核空间的 Datapath 模块传输至用户空间的 ovs-vswitchd 守护进…