滑动窗口经典入门题-——长度最小子数组
文章目录
- 算法原理
- 题目解析
- 暴力枚举法的代码
- 优化
- 第一步初始化
- 第二步right右移
- 第三步left右移
- 滑动窗口法的代码
算法原理
滑动窗口是一种在序列(例如数组或链表)上解决问题的算法模式。它通常用于解决子数组或子字符串的问题,其中滑动窗口表示一个范围,这个范围在序列上移动,以便找到满足特定条件的子数组或子字符串。
算法的基本思想是维护两个指针,通常是左右两个指针,表示滑动窗口的左右边界。通过调整这两个指针,可以滑动窗口在序列上移动。在每个窗口位置,都可以根据问题的要求进行处理,比如计算窗口内的和、最大值、最小值,或者检测满足某些条件的子数组或子字符串等。
滑动窗口算法的一般步骤如下:
初始化左右指针: 将左指针和右指针初始化为序列的起始位置。
滑动窗口: 移动右指针以扩大窗口,或移动左指针以缩小窗口,直到满足问题的条件。
处理窗口数据: 在每个窗口位置,根据问题的要求处理窗口内的数据,比如计算窗口内的和、最大值、最小值,或者检测满足某些条件的子数组或子字符串。
更新结果: 根据问题的要求更新结果。
重复: 重复2-4步骤,直到右指针到达序列的末尾。
滑动窗口算法通常能够在线性时间内解决一些与子数组或子字符串相关的问题,因为每个元素至多被访问两次(一次由左指针,一次由右指针)。这种算法的时间复杂度通常是 O(N),其中 N 是序列的长度。
实际应用中,滑动窗口算法可以解决一系列问题,如最大子数组和、最小覆盖子串、最长无重复字符子串等。
题目解析
废话不多说先上题目链接leetcode—长度最小子数组
那么接下来我们一起解析一下例题如下图

首先最重要的肯定是读懂题目,题目意思其实也很容易读懂意思就是给我们一个数字target和一个数组,要求在这个数组中找到一个必须是连续的子数组并且这个子数组每个元素加起来>=target并从找到的这些数组中取一个最短的数组那么炸一看可能会感觉有些茫然,但是学习算法我们要记住一个步骤就是面对一个题目的时候先想一下如何暴力的把他求出来,那么很简单那就是找到所有的子数组并从这些子数组中找到和>=target的数组之后取得最小值那么我们把暴力的方法先写出来代码如下
暴力枚举法的代码
class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int ans=0x9f9f9f;for(int i=0;i<nums.size();i++){int t=0;for(int j=i;j<nums.size();j++){t+=nums[j];if(i==j){if(t>=target){ans=min(ans,j-i+1);break;}}if(t>=target){ans=min(ans,j-i+1);break;}}}if(ans==0x9f9f9f){return 0;}return ans;}
};

由于力扣的后台测试数据比较小所以这个暴力的解法也可以过但是我们可以清楚的看到这个算法的时间复杂度达到了O(n^2)因此这个时间负责度还是比较高的因此我们有没有更简单的办法呢?
优化
使用滑动窗口进行优化,
在这道题目中我们可以看到两个重要信息
1、子数组必须是连续的
2、子数组的和需要>=target
那么我们可以想一下我们可以使用两个指针一个是left一个是right当left和right之间的元素和小于target的时候就让right一直向右移动,当right和left之间的元素大于等于target的时候我们更新一下此时的长度是否为最短,然后再让left左移查看此时right和left的元素之和是否大于等于target如果是就继续上一步操作即继续更新我们的最短长度,一直到right和left之间的数据小于target为止之后再让right指针右移即可。
我给大家举出一个例子说明一下。
第一步初始化

第二步right右移

此时我们可以发现right和left之间的元素和超过了target因此我们与目标值进行比较取得较小的那个然后让left右移之后再进行查看此时right和left之间的元素和是否大于等于target。
第三步left右移

此时我们右移后发现right和left之间的元素和小于target因此right继续右移然后后续一直重复这个操作即可
滑动窗口法的代码
class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int left=0;int right=0;int sum=nums[0];int ansmin=100010;while(right<nums.size()&&left<nums.size()){if(sum>=target){ansmin=min(right-left+1,ansmin);sum-=nums[left];left++;}else{right++;if(right<nums.size())sum+=nums[right];else break;}}if(ansmin==100010){return 0;}return ansmin;}
};

我们可以从用时分布图清楚的看到我们的时间效率有了很大的提升。
相关文章:
滑动窗口经典入门题-——长度最小子数组
文章目录 算法原理题目解析暴力枚举法的代码优化第一步初始化第二步right右移第三步left右移 滑动窗口法的代码 算法原理 滑动窗口是一种在序列(例如数组或链表)上解决问题的算法模式。它通常用于解决子数组或子字符串的问题,其中滑动窗口表示…...
AcGeMatrix2d::alignCoordSys一种实现方式
问题描述 此处为了简化问题,在2维空间中处理,按以下方式调用,AcGeMatrix2d::alignCoordSys是如何求出一个矩阵的呢,这里提供一个实现思路(但效率不保证好) AcGeMatrix2d matTrans AcGeMatrix2d::alignCo…...
InternLM第5次课笔记
LMDeploy 大模型量化部署实践 1 大模型部署背景 2 LMDeploy简介 3 动手实践环节 https://github.com/InternLM/tutorial/blob/main/lmdeploy/lmdeploy.md 3...
2018年认证杯SPSSPRO杯数学建模D题(第一阶段)投篮的最佳出手点全过程文档及程序
2018年认证杯SPSSPRO杯数学建模 对于投篮最佳出手点的探究 D题 投篮的最佳出手点 原题再现: 影响投篮命中率的因素不仅仅有出手角度、球感、出手速度,还有出手点的选择。规范的投篮动作包含两膝微屈、重心落在两脚掌上、下肢蹬地发力、身体随之向前上…...
使用pdfbox 为 PDF 增加水印
使用pdfbox 为 PDF增加水印https://www.jylt.cc/#/detail?activityIndex2&idbd410851b0a72dad3105f9d50787f914 引入依赖 <dependency><groupId>org.apache.pdfbox</groupId><artifactId>pdfbox</artifactId><version>3.0.1</ve…...
6.【CPP】Date类的实现
Date.h #pragma once using namespace std; #include<iostream>class Date {friend ostream& operator<<(ostream& out, const Date& d);friend istream& operator>>(istream& in, Date& d); public://构造函数会被频繁调用,放在类…...
三角形任意一外角大于不相邻的任意一内角
一.代数证明 ∵ 对与△ A C B 中 ∠ c 外接三角形是 ∠ B C D ∵对与△ACB中∠c外接三角形是∠BCD ∵对与△ACB中∠c外接三角形是∠BCD ∴ ∠ B C D π − ∠ C ∴∠BCD\pi-∠C ∴∠BCDπ−∠C ∵ ∠ A ∠ B ∠ C π ∵∠A∠B∠C\pi ∵∠A∠B∠Cπ ∴ ∠ B C D ∠ A ∠…...
【Spring Boot 3】【Redis】集成Lettuce
【Spring Boot 3】【Redis】集成Lettuce 背景介绍开发环境开发步骤及源码工程目录结构总结背景 软件开发是一门实践性科学,对大多数人来说,学习一种新技术不是一开始就去深究其原理,而是先从做出一个可工作的DEMO入手。但在我个人学习和工作经历中,每次学习新技术总是要花…...
【SQL注入】SQLMAP v1.7.11.1 汉化版
下载链接 【SQL注入】SQLMAP v1.7.11.1 汉化版 简介 SQLMAP是一款开源的自动化SQL注入工具,用于扫描和利用Web应用程序中的SQL注入漏洞。它在安全测试领域被广泛应用,可用于检测和利用SQL注入漏洞,以验证应用程序的安全性。 SQL注入是一种…...
时序预测 | MATLAB实现GRNN广义回归神经网络时间序列未来多步预测(程序含详细预测步骤)
时序预测 | MATLAB实现GRNN广义回归神经网络时间序列未来多步预测(程序含详细预测步骤) 目录 时序预测 | MATLAB实现GRNN广义回归神经网络时间序列未来多步预测(程序含详细预测步骤)预测效果基本介绍程序设计参考资料预测效果 基本介绍 MATLAB实现GRNN广义回归神经网络时间序列…...
长期戴耳机的危害有哪些?戴哪种耳机不伤耳朵听力?
长期佩戴耳机可能会出现听力下降、耳道感染等危害。 听力下降:长时间戴耳机可能会导致耳道内的声音过大,容易对耳膜造成一定的刺激,容易出现听力下降的情况。 耳道感染:长时间戴耳机,耳道长期处于封闭潮湿的情况下&a…...
C++中的预处理
一.预定义符号 1.__FILE__进行编译的源文件 2.__LINE__文件当前的行号 3.__DATE__文件被编译的日期 4.__TIME文件被编译的时间 5.__STDC__如果编译器遵循ANSIC,其值为1,否则未定义 二.#define 基本语法:#define 名字 内容 eg.define M 1 经#define定义的常量时不经过…...
flink 最后一个窗口一直没有新数据,窗口不关闭问题
flink 最后一个窗口一直没有新数据,窗口不关闭问题 自定义实现 WatermarkStrategy接口 自定义实现 WatermarkStrategy接口 窗口类型:滚动窗口 代码: public static class WatermarkDemoFunction implements WatermarkStrategy<JSONObject…...
mybatis----小细节
1、起别名 在MyBatis中,<typeAliases>元素用于定义类型别名,它可以将Java类名映射为一个更简短的别名,这样在映射文件中可以直接使用别名而不需要完整的类名。 下面是一个示例: 在mybatis核心配置文件中配置typeAliases标…...
解密Oracle数据库引擎:揭开数据存储的神秘面纱
目录 1、介绍Oracle数据库引擎 1.1 什么是Oracle数据库引擎 1.2 Oracle数据库引擎的作用和功能 1.3 Oracle数据库引擎的历史和发展 2、Oracle数据库引擎的体系结构 2.1 Oracle数据库实例的组成部分 2.2 Oracle数据库引擎的层次结构 2.3 Oracle数据库引擎的关键组件 3、…...
「HDLBits题解」Karnaugh Map to Circuit
本专栏的目的是分享可以通过HDLBits仿真的Verilog代码 以提供参考 各位可同时参考我的代码和官方题解代码 或许会有所收益 相关资料:卡诺图化简法-CSDN博客 题目链接:Kmap1 - HDLBits module top_module(input a,input b,input c,output out );assig…...
由于找不到d3dcompiler_43.dll缺失,无法打开软件的解决方法分享
d3dcompiler43.dll是什么文件?为什么会出现丢失的情况?又该如何解决呢?本文将详细介绍d3dcompiler43.dll的作用和影响,并提供6个有效的解决方法。 一、d3dcompiler43.dll是什么文件? d3dcompiler43.dll是DirectX SDK…...
现阶段Python和Java哪个更吃香?
现阶段Python和Java哪个更吃香? 在开始前我有一些资料,是我根据网友给的问题精心整理了一份「Java的资料从专业入门到高级教程」, 点个关注在评论区回复“888”之后私信回复“888”,全部无偿共享给大家!!&…...
基于DNA的密码学和隐写术综述
摘要 本文全面调研了不同的脱氧核糖核酸(DNA)-基于密码学和隐写术技术。基于DNA的密码学是一个新兴领域,利用DNA分子的大规模并行性和巨大的存储容量来编码和解码信息。近年来,由于其相对传统密码学方法的潜在优势,如高存储容量、低错误率和对环境因素的抗性,该领域引起…...
【linux 多线程并发】多线程的控制,挂起线程暂停运行,直到唤醒线程,取消线程运行,可以设置合适的取消点属性避免不安全点被中止
线程运行控制 专栏内容: 参天引擎内核架构 本专栏一起来聊聊参天引擎内核架构,以及如何实现多机的数据库节点的多读多写,与传统主备,MPP的区别,技术难点的分析,数据元数据同步,多主节点的情况…...
用Artisan构建专业级咖啡烘焙解决方案:从数据采集到品质优化的全流程指南
用Artisan构建专业级咖啡烘焙解决方案:从数据采集到品质优化的全流程指南 【免费下载链接】artisan artisan: visual scope for coffee roasters 项目地址: https://gitcode.com/gh_mirrors/ar/artisan 在咖啡产业数字化转型的浪潮中,专业烘焙师正…...
专业级视频对比分析工具:video-compare的技术架构深度解析
专业级视频对比分析工具:video-compare的技术架构深度解析 【免费下载链接】video-compare Split screen video comparison tool using FFmpeg and SDL2 项目地址: https://gitcode.com/gh_mirrors/vi/video-compare 在视频编码质量评估、算法效果验证和媒体…...
从ChatGPT到机器翻译:GRPO算法如何优化大语言模型的生成效果?
GRPO算法:大语言模型生成效果优化的新范式 在自然语言处理领域,序列生成任务的质量优化一直是研究热点。从ChatGPT的对话流畅度到机器翻译的准确性,生成效果直接影响用户体验。传统优化方法如PPO虽然有效,但在处理复杂语言任务时存…...
ComfyUI-WanVideoWrapper视频生成工具零基础快速部署实战教程
ComfyUI-WanVideoWrapper视频生成工具零基础快速部署实战教程 【免费下载链接】ComfyUI-WanVideoWrapper 项目地址: https://gitcode.com/GitHub_Trending/co/ComfyUI-WanVideoWrapper ComfyUI-WanVideoWrapper是一款功能强大的视频生成工具,它能让用户在Co…...
hgproxy偶发性无法连接
文章目录环境症状问题原因解决方案环境 系统平台:银河麒麟 (鲲鹏) 版本:4.5.8 症状 hgproxy 4.0.33.3 出现偶发性无法连接现象,经过几分钟或几十秒或更长时间会自动恢复正常;psql 连接数据库端口正常&am…...
APKMirror:安卓应用安全管理的终极解决方案
APKMirror:安卓应用安全管理的终极解决方案 【免费下载链接】APKMirror 项目地址: https://gitcode.com/gh_mirrors/ap/APKMirror 您是否曾在寻找安卓应用的特定版本时感到无从下手?是否担忧从第三方渠道下载的APK文件可能存在安全隐患ÿ…...
LabelMe企业级部署方案:多用户权限管理与审计
LabelMe企业级部署方案:多用户权限管理与审计 LabelMe是一款强大的图像标注工具,支持多边形、矩形、圆形等多种标注形式,广泛应用于计算机视觉领域的数据准备工作。在企业环境中部署LabelMe时,多用户权限管理与操作审计是确保数据…...
brpc代码重构原则:保持兼容性与提升性能并重的终极指南
brpc代码重构原则:保持兼容性与提升性能并重的终极指南 【免费下载链接】brpc brpc is an Industrial-grade RPC framework using C Language, which is often used in high performance system such as Search, Storage, Machine learning, Advertisement, Recomme…...
如何为你的单片机项目选择最佳通信协议?I²C、SPI、UART全解析
单片机通信协议深度指南:从理论到实战的精准选择策略 当你的单片机需要与外部世界对话时,选择正确的通信协议就像为不同场合挑选合适的语言——商务会议需要正式严谨,朋友聊天则讲究轻松随意。在嵌入式系统设计中,UART、IC和SPI这…...
免费解锁付费内容:Bypass Paywalls Clean Chrome扩展终极指南
免费解锁付费内容:Bypass Paywalls Clean Chrome扩展终极指南 【免费下载链接】bypass-paywalls-chrome-clean 项目地址: https://gitcode.com/GitHub_Trending/by/bypass-paywalls-chrome-clean 在数字阅读时代,你是否经常遇到想阅读的文章被付…...
