滑动窗口实例1(长度最小的子数组)

题目:

给定一个含有 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 <= 109
  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 105

算法原理:

暴力解法基础上的优化:

暴力解法是依次固定左边界,从左边界开始依次作为右边界加入sum,计算和,当和>=target且小于上一次的结果就更新结果

暴力解法存在很多不必要且重复的计算:

滑动窗口(优解):

 滑动窗口其实就是同向指针,left指针和right指针都不会回退

初始化:left=0 (左边界)right=0(待进入窗口的数值)

1 进窗口:让right指针指向的数值加入sum中

2 判断:若是sum>=target(已是当前left指向数值作为左边界找到的满足条件的最短连续子数组,right指针没必要往后面走,再让sum加入一些数值,因为只要再加入数值,一定是比target大的,但是又增加了长度,所以没必要)  且比上一次的结果要小则更新结果

 3 出窗口:left指向的数值作为左边界已有自己的最优结果,sum-=nums[left++]

    重复步骤2的判断,因为出了原先的nums[left] ,新数值作为左边界时也可能已经满足条件              sum>=target(right指针依然是原nums[left]做左边界时,能够找到的最优右边界),如right指向的数值加入后使得sum远远大于target,那么出了一个元素,可能会使得剩下的元素依然>=target

4 结束条件:right>=n 

代码实现:

 

class Solution 
{
public:int minSubArrayLen(int target, vector<int>& nums){int sum = 0;int len = INT_MAX;//注意不能初始化为0,因为是找最小int left = 0;int right = 0;int n = nums.size(); while(right<n){sum+=nums[right];//进窗口while(sum>=target)//判断{len = min(len,right-left+1);//更新结果sum-=nums[left++];//出窗口}right++;}return len==INT_MAX?0:len;}
};

            

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

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

相关文章

zookeeper 3.8.1安装和入门使用

1、zookeeper环境搭建&#xff08;Windows单机版&#xff09; 1.1、 前提 必须安装jdk 1.8&#xff0c;配置jdk环境变量&#xff0c;步骤略 1.2、安装zookeeper 地址&#xff1a;https://zookeeper.apache.org/ 1.2.1、选择releases版本 1.2.2、下载安装包并解压 1.2.3、配…

前端文件、图片直传OOS、分片上传、el-upload上传(vue+elementUI)

前言&#xff1a;基于天翼云的面相对象存储(Object-Oriented Storage&#xff0c;OOS),实现小文件的直接上传&#xff0c;大文件的分片上传。 开发文档地址&#xff1a;网址 上传之前的相关操作&#xff1a;注册账户&#xff0c;创建 AccessKeyId 和 AccessSecretKey之后&…

企业怎么优化固定资产管理

在优化固定资产管理的过程中&#xff0c;不仅要关注硬件设备和设施的维护&#xff0c;还要重视软件系统和数据管理。一些可能的方法&#xff1a;  需要建立一套完整的资产管理系统。这个系统应该包括资产的采购、登记、使用、维修、报废等各个环节的管理流程。通过这个系统&a…

智慧工地源码带开发手册文档 app 数据大屏、硬件对接、萤石云

智慧工地解决方案依托计算机技术、物联网、云计算、大数据、人工智能、VR、AR等技术相结合&#xff0c;为工程项目管理提供先进技术手段&#xff0c;构建工地现场智能监控和控制体系&#xff0c;弥补传统方法在监管中的缺陷&#xff0c;最终实现项目对人、机、料、法、环的全方…

Windows安装FFmpeg说明

下载地址 官网 Download FFmpeg Csdn ffmpeg安装包&#xff0c;ffmpeg-2023-08-28-git-b5273c619d-full-build.7z资源-CSDN文库 解压安装&#xff0c;添加环境变量 命令行输入ffmpeg 安装成功

【mysql】MySQL服务无法启动 NET HELPMSG 3534

MySQL服务无法启动 NET HELPMSG 3534 错误描述寻找原因解决方法 错误描述 mysql版本&#xff1a;8.1.0 mysql安装成功之后&#xff0c;使用net start mysql来启动mysql&#xff0c;然后出现了报错 MySQL服务无法启动 NET HELPMSG 3534 寻找原因 1、在cmd中&#xff0c;进入…

React 如何获取上一次 state 的值

React 如何获取上一次 state 的值 一、用 ref 存储上一次的 state 类似 usePrevious function usePrevious(value) {const ref useRef();useEffect(() > {ref.current value;});return ref.current; }二、通过 setState 的入参改为函数获取

electron win系统通知修改通知标题栏

标题栏的 electron.app.Electron 如何修改&#xff1a; var package require("../package.json"); app.setAppUserModelId(package.description); app.setAppUserModelId 在主进程的app这里修改

Flutter 混合开发调试

针对Flutter开发的同学来说&#xff0c;大部分的应用还是Native Flutter的混合开发&#xff0c;所以每次改完Flutter代码&#xff0c;运行整个项目无疑是很费时间的。所以Flutter官方也给我们提供了混合调试的方案【在混合开发模式下进行调试】&#xff0c;这里以Android Stud…

【openEuler创新项目探索】一个Java端的向量化BLAS库VectorBLAS

VectorBLAS简介 VectorBLAS是一个使用Java语言实现的向量化BLAS高性能库&#xff0c;目前已在openEuler社区开源。 VectorBLAS通过循环展开、矩阵分块和内存布局优化等算法优化&#xff0c;对BLAS函数进行了深度优化&#xff0c;并利用VectorAPI JDK提供的多种向量化API实现。…

Baklib是比语雀、Notion、石墨文档更好用的在线知识库管理工具

在当今信息爆炸的时代&#xff0c;如何高效地管理和利用知识成为了每个人都面临的问题。在线知识库管理工具应运而生&#xff0c;帮助用户整理、存储和共享知识。在这篇文章中&#xff0c;我将介绍一个更好用的在线知识库管理工具——Baklib&#xff0c;并探讨它相对于其他知识…

PMAC与Modbus主站进行Modbus Tcp通讯

PMAC与Modbus主站进行Modbus Tcp通讯 创建modbus通讯参数 在项目的PMAC Script Language\Global Includes下创建一个名为00_Modbus_Para.pmh的pmh文件。 Modbus[0].Config.ServerPort 0 Modbus[0].Config.ConnectTimeOut 6000 Modbus[0].Config.SendRecvTimeOut 0 Modbu…

利用Jmeter做接口测试(功能测试)全流程分析

利用Jmeter做接口测试怎么做呢&#xff1f;过程真的是超级简单。 明白了原理以后&#xff0c;把零碎的知识点填充进去就可以了。所以在学习的过程中&#xff0c;不管学什么&#xff0c;我一直都强调的是要循序渐进&#xff0c;和明白原理和逻辑。这篇文章就来介绍一下如何利用…

【机器学习7】特征缩放

特征缩放 &#x1f340;特征缩放的重要性&#x1f331;归一化&#x1f331;标准化&#x1f331;更高级的缩放方法&#x1f338;导入数据集&将数据集划分为训练集和测试集&#x1f338;Sklearn-Learn算法实现归一化&#x1f338;Sklearn-Learn算法实现标准化 &#x1f340;特…

Google登录SDK

一、接入的准备工作 官方文档链接地址&#xff1a;开始使用一键登录和注册 按照步骤进行接入即可 二、项目参考&#xff08;Unity项目&#xff09; 注意&#xff1a;代码版本如果不适用新的Google API 请自行参考最新版本接口 SDKGoogleSignInActivity 主要用于登录的代码。Un…

[Linux]进程程序替换

[Linux]进程程序替换 文章目录 [Linux]进程程序替换进程程序替换的意义见一见进程程序替换进程程序替换的原理进程程序替换中的写时拷贝介绍进程程序替换接口 进程程序替换的意义 Linux系统下使用fork系统函数创建子进程后&#xff0c;子进程只能执行继承的部分父进程代码&…

108页石油石化5G智慧炼化厂整体方案PPT

导读:原文《108页石油石化5G智慧炼化厂整体方案PPT》(获取来源见文尾),本文精选其中精华及架构部分,逻辑清晰、内容完整,为快速形成售前方案提供参考。以下是部分内容,

Redis7之介绍(一)

1. 是什么 Redis:REmote Dictionary Server(远程字典服务器&#xff09; Remote Dictionary Server( 远程字典服务)是完全开源的&#xff0c;使用ANSIC语言编写遵守BSD协议&#xff0c;是一个高性能的Key-Value数据库提供了丰富的数据结构&#xff0c;例如String、Hash、List、…

电商数仓项目需求及架构设计

一、项目需求 1.用户行为数据采集平台搭建 2.业务数据采集平台搭建 3.数仓维度建模 4.统计指标 5.即席查询工具&#xff0c;随时进行指标分析 6.对集群性能进行监控&#xff0c;发生异常时报警&#xff08;第三方信息&#xff09; 7.元数据管理 8.质量监控 9.权限管理&#xff…

浅谈Lua协程和函数的尾调用

前言 虽然不经常用到协程&#xff0c;但是也不能谈虎色变。同时&#xff0c;在有些场景&#xff0c;协程会起到一种不可比拟的作用。所以&#xff0c;了解它&#xff0c;对于一些功能&#xff0c;也会有独特的思路和想法。 协程 概念 关于进程和线程的概念就不多说。 那么…