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

滑动窗口经典入门题-——长度最小子数组

文章目录

  • 算法原理
  • 题目解析
  • 暴力枚举法的代码
  • 优化
    • 第一步初始化
    • 第二步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右移 滑动窗口法的代码 算法原理 滑动窗口是一种在序列&#xff08;例如数组或链表&#xff09;上解决问题的算法模式。它通常用于解决子数组或子字符串的问题&#xff0c;其中滑动窗口表示…...

AcGeMatrix2d::alignCoordSys一种实现方式

问题描述 此处为了简化问题&#xff0c;在2维空间中处理&#xff0c;按以下方式调用&#xff0c;AcGeMatrix2d::alignCoordSys是如何求出一个矩阵的呢&#xff0c;这里提供一个实现思路&#xff08;但效率不保证好&#xff09; 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题 投篮的最佳出手点 原题再现&#xff1a; 影响投篮命中率的因素不仅仅有出手角度、球感、出手速度&#xff0c;还有出手点的选择。规范的投篮动作包含两膝微屈、重心落在两脚掌上、下肢蹬地发力、身体随之向前上…...

使用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注入工具&#xff0c;用于扫描和利用Web应用程序中的SQL注入漏洞。它在安全测试领域被广泛应用&#xff0c;可用于检测和利用SQL注入漏洞&#xff0c;以验证应用程序的安全性。 SQL注入是一种…...

时序预测 | MATLAB实现GRNN广义回归神经网络时间序列未来多步预测(程序含详细预测步骤)

时序预测 | MATLAB实现GRNN广义回归神经网络时间序列未来多步预测(程序含详细预测步骤) 目录 时序预测 | MATLAB实现GRNN广义回归神经网络时间序列未来多步预测(程序含详细预测步骤)预测效果基本介绍程序设计参考资料预测效果 基本介绍 MATLAB实现GRNN广义回归神经网络时间序列…...

长期戴耳机的危害有哪些?戴哪种耳机不伤耳朵听力?

长期佩戴耳机可能会出现听力下降、耳道感染等危害。 听力下降&#xff1a;长时间戴耳机可能会导致耳道内的声音过大&#xff0c;容易对耳膜造成一定的刺激&#xff0c;容易出现听力下降的情况。 耳道感染&#xff1a;长时间戴耳机&#xff0c;耳道长期处于封闭潮湿的情况下&a…...

C++中的预处理

一.预定义符号 1.__FILE__进行编译的源文件 2.__LINE__文件当前的行号 3.__DATE__文件被编译的日期 4.__TIME文件被编译的时间 5.__STDC__如果编译器遵循ANSIC,其值为1,否则未定义 二.#define 基本语法:#define 名字 内容 eg.define M 1 经#define定义的常量时不经过…...

flink 最后一个窗口一直没有新数据,窗口不关闭问题

flink 最后一个窗口一直没有新数据&#xff0c;窗口不关闭问题 自定义实现 WatermarkStrategy接口 自定义实现 WatermarkStrategy接口 窗口类型&#xff1a;滚动窗口 代码&#xff1a; public static class WatermarkDemoFunction implements WatermarkStrategy<JSONObject…...

mybatis----小细节

1、起别名 在MyBatis中&#xff0c;<typeAliases>元素用于定义类型别名&#xff0c;它可以将Java类名映射为一个更简短的别名&#xff0c;这样在映射文件中可以直接使用别名而不需要完整的类名。 下面是一个示例&#xff1a; 在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代码 以提供参考 各位可同时参考我的代码和官方题解代码 或许会有所收益 相关资料&#xff1a;卡诺图化简法-CSDN博客 题目链接&#xff1a;Kmap1 - HDLBits module top_module(input a,input b,input c,output out );assig…...

由于找不到d3dcompiler_43.dll缺失,无法打开软件的解决方法分享

d3dcompiler43.dll是什么文件&#xff1f;为什么会出现丢失的情况&#xff1f;又该如何解决呢&#xff1f;本文将详细介绍d3dcompiler43.dll的作用和影响&#xff0c;并提供6个有效的解决方法。 一、d3dcompiler43.dll是什么文件&#xff1f; d3dcompiler43.dll是DirectX SDK…...

现阶段Python和Java哪个更吃香?

现阶段Python和Java哪个更吃香&#xff1f; 在开始前我有一些资料&#xff0c;是我根据网友给的问题精心整理了一份「Java的资料从专业入门到高级教程」&#xff0c; 点个关注在评论区回复“888”之后私信回复“888”&#xff0c;全部无偿共享给大家&#xff01;&#xff01;&…...

基于DNA的密码学和隐写术综述

摘要 本文全面调研了不同的脱氧核糖核酸(DNA)-基于密码学和隐写术技术。基于DNA的密码学是一个新兴领域,利用DNA分子的大规模并行性和巨大的存储容量来编码和解码信息。近年来,由于其相对传统密码学方法的潜在优势,如高存储容量、低错误率和对环境因素的抗性,该领域引起…...

【linux 多线程并发】多线程的控制,挂起线程暂停运行,直到唤醒线程,取消线程运行,可以设置合适的取消点属性避免不安全点被中止

线程运行控制 ​专栏内容&#xff1a; 参天引擎内核架构 本专栏一起来聊聊参天引擎内核架构&#xff0c;以及如何实现多机的数据库节点的多读多写&#xff0c;与传统主备&#xff0c;MPP的区别&#xff0c;技术难点的分析&#xff0c;数据元数据同步&#xff0c;多主节点的情况…...

3分钟掌握Windows音频路由:让每个程序都有专属音频输出 [特殊字符]

3分钟掌握Windows音频路由&#xff1a;让每个程序都有专属音频输出 &#x1f3a7; 【免费下载链接】audio-router Routes audio from programs to different audio devices. 项目地址: https://gitcode.com/gh_mirrors/au/audio-router 你是否曾经遇到过这样的烦恼&…...

InfluxDB服务文件被误删怎么办?记录一次完整的1.8.6版本灾难恢复过程

InfluxDB服务文件误删灾难恢复实录&#xff1a;从崩溃边缘到完美复原 那天下午&#xff0c;服务器监控大屏突然亮起一片刺眼的红色告警——InfluxDB服务全线离线。作为团队里负责时序数据库运维的老兵&#xff0c;我立刻意识到问题的严重性。这套运行着1.8.6版本的InfluxDB承载…...

M3U8 开发调试神器!m3u8live.cn轻量在线播放器高效解决流媒体开发痛点

在音视频开发、直播推流、点播平台搭建的日常工作中&#xff0c;M3U8 链接有效性验证、HLS 流播放调试是高频刚需。传统方案要么需要安装 VLC 等本地播放器进行繁琐的网络串流配置&#xff0c;要么第三方工具广告泛滥、兼容性差&#xff0c;甚至需要编写测试代码才能完成简单的…...

TWS耳机充电仓硬件设计全解析:从Type-C接口到NTC保护的7大核心模块

TWS耳机充电仓硬件设计全解析&#xff1a;从Type-C接口到NTC保护的7大核心模块 当你在咖啡馆掏出AirPods时&#xff0c;可能不会想到那个小巧的充电仓里藏着多少精密电路。作为硬件工程师&#xff0c;我们眼中的充电仓不是简单的塑料盒子&#xff0c;而是一个由七大核心模块组成…...

ChatTTS一键启动:从零搭建语音合成服务的实战指南

语音合成服务在现代应用中扮演着越来越重要的角色。它被广泛应用于智能客服、有声读物生成和视频内容配音等场景。通过将文本转化为自然流畅的语音&#xff0c;极大地提升了人机交互的体验和应用的可访问性。 然而&#xff0c;对于希望快速部署ChatTTS这类先进语音合成模型的开…...

OpenRocket:重新定义模型火箭设计与仿真的开源力量

OpenRocket&#xff1a;重新定义模型火箭设计与仿真的开源力量 【免费下载链接】openrocket Model-rocketry aerodynamics and trajectory simulation software 项目地址: https://gitcode.com/GitHub_Trending/op/openrocket 核心价值&#xff1a;破解模型火箭开发的效…...

别再用yield了!FastAPI 2.0官方弃用警告下的流式响应新范式(含ASGI StreamingResponse + async iterator最佳实践)

第一章&#xff1a;FastAPI 2.0流式响应弃用背景与演进动因FastAPI 2.0 将 StreamingResponse 的默认行为从“自动分块传输”转向显式、可控的流式语义&#xff0c;其核心动因源于对 HTTP/1.1 分块编码&#xff08;Chunked Transfer Encoding&#xff09;与现代客户端&#xff…...

Linux字符设备驱动开发与核心架构解析

Linux字符设备驱动开发深度解析1. Linux设备驱动分类与架构Linux内核将设备驱动分为三大类型&#xff1a;字符设备驱动&#xff1a;以字节流形式进行数据读写&#xff0c;如串口、键盘等块设备驱动&#xff1a;以固定大小数据块为单位进行操作&#xff0c;如硬盘、U盘等网络设备…...

FFmpeg 全链路中间件深度分析

一、开源代码目录文件树形分析1.1 FFmpeg 源码整体架构树FFmpeg ├── configure # 配置脚本&#xff08;生成config.h/config.mak&#xff09; ├── Makefile # 顶层Makefile ├── Changelog # 版本变更…...

Python张量框架选型不是技术问题,而是组织问题:CTO必须在立项前确认的5个战略问题(含人才储备周期、长期维护成本、专利风险审计清单)

第一章&#xff1a;Python张量框架选型不是技术问题&#xff0c;而是组织问题当团队在 PyTorch、TensorFlow 和 JAX 之间反复争论“哪个性能更好”或“哪个 API 更优雅”时&#xff0c;往往已陷入技术决定论的误区。真正制约张量框架落地效果的&#xff0c;是组织内部的协同惯性…...