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

「算法」滑动窗口

前言

算法需要多刷题积累经验,所以我行文重心在于分析解题思路,理论知识部分会相对简略一些

正文

滑动窗口属于双指针,这两个指针是同向前行,它们所夹的区间就称为“窗口”

啥时候用滑动窗口?

  • 题目涉及到“子序列”、“子数组”、“子串”等概念,要你求和它们相关的量,比如求满足条件的子数组的最大长度
  • 在暴力枚举的时候,如果发现两个“指针”都是朝同一个方向走的,就可以考虑滑动窗口
    注:滑动窗口可以看作是暴力枚举优化后的结果

如何使用?(步骤)

  1. 定义两个“指针”left、right(此“指针”不是真正的指针)
  2. 通过移动 right 让元素进窗口
  3. 进窗口之后进行判断,并根据这个判断决定什么时候需要出窗口

2和3需要放在一个循环里面,这样才可以让窗口不断往前走

  • 在移动“窗口”的过程我们需要不断更新结果,比如求子数组最大长度maxLen,那么每次求出一个子数组长度之后,我们就要判断是否需要更新maxLen
  • 至于是在进窗口后更新结果,还是在出窗口后更新,这就需要结合具体题目分析

例题

长度最小的子数组

思路

  1. 先用暴力枚举看看怎么做,我们先固定一个端点left,然后让right一直往右走,直到[left,right]区间中的元素和大于target,此时得到区间长度为right-left+1
  2. 既然已经比target大,那接下来就别让right往右走了,先让它停下来,因为数组中全是正数,此时right继续走的话,区间中元素总和肯定还是比target大,但是此时区间的长度肯定不是最小长度,这样就做了无用功
  3. 所以我们应该让left向前走,缩小区间,将新区间的元素和与 target 比较,若大于 target,则记录此时区间长度,并让 left 继续向前走;反之则让 right 往前走

在这里插入图片描述

上面的思路其实就是从暴力枚举逐步过渡到滑动窗口,整个过程下来,我们不难发现:砍掉暴力枚举中那些无用功,也就得到滑动窗口的思路了

代码如下:

class Solution {public int minSubArrayLen(int target, int[] nums) {int left = 0,right = 0;  //区间为左闭右闭int sum = 0;  //区间中元素总和int minLen = nums.length+1;  //最小窗口的长度,一开始初始化为一个比较大的数,不然下面使用取小函数可能没法正确更新minLenfor(;right < nums.length;right++) {sum += nums[right];while(sum >= target) {minLen = Math.min(minLen,right-left+1);  //更新 minLensum -= nums[left];left++;}}return minLen == nums.length+1 ? 0 : minLen;}
}

注意:用取小函数来更新 minLen,可以简化代码(相比于使用条件语句判断大小),同理,可以用取大函数来更新最大值

复杂度分析

时间复杂度:O(N),最坏情况下左右指针都要走完整个数组
比如数组大小为5,前四个元素都为1,最后一个为10000,target为10
空间复杂度:O(1)

相关文章:

「算法」滑动窗口

前言 算法需要多刷题积累经验&#xff0c;所以我行文重心在于分析解题思路&#xff0c;理论知识部分会相对简略一些 正文 滑动窗口属于双指针&#xff0c;这两个指针是同向前行&#xff0c;它们所夹的区间就称为“窗口” 啥时候用滑动窗口&#xff1f; 题目涉及到“子序列…...

Windows11(非WSL)安装Installing llama-cpp-python with GPU Support

直接安装&#xff0c;只支持CPU。想支持GPU&#xff0c;麻烦一些。 1. 安装CUDA Toolkit (NVIDIA CUDA Toolkit (available at https://developer.nvidia.com/cuda-downloads) 2. 安装如下物件&#xff1a; gitpythoncmakeVisual Studio Community (make sure you install t…...

rtt设备io框架面向对象学习-脉冲编码器设备

目录 1.脉冲编码器设备基类2.脉冲编码器设备基类的子类3.初始化/构造流程3.1设备驱动层3.2 设备驱动框架层3.3 设备io管理层 4.总结5.使用 1.脉冲编码器设备基类 此层处于设备驱动框架层。也是抽象类。 在/ components / drivers / include / drivers 下的pulse_encoder.h定义…...

华为OD机试真题- 攀登者2-2024年OD统一考试(C卷)

题目描述: 攀登者喜欢寻找各种地图,并且尝试攀登到最高的山峰。地图表示为一维数组,数组的索引代表水平位置,数组的高度代表相对海拔高度。其中数组元素0代表地面。例如[0,1,4,3,1,0,0,1,2,3,1,2,1,0], 代表如下图所示的地图,地图中有两个山脉位置分别为 1,2,3,4,5和8,9,1…...

19.Qt 组合框的实现和应用

目录 前言&#xff1a; 技能&#xff1a; 内容&#xff1a; 1. 界面 2.槽 3.样式表 参考&#xff1a; 前言&#xff1a; 学习QCombox控件的使用 技能&#xff1a; 简单实现组合框效果 内容&#xff1a; 1. 界面 在ui编辑界面找到input widget里面的comboBox&#xff…...

【Linux】进程地址空间的理解

进程地址空间的理解 一&#xff0c;什么是程序地址空间二&#xff0c;页表和虚拟地址空间三&#xff0c;为什么要有进程地址空间 一&#xff0c;什么是程序地址空间 在我们写程序时&#xff0c;都会有这样下面的内存结构&#xff0c;来存放变量和代码等数据。 一个进程要执行…...

【Jvm】类加载机制(Class Loading Mechanism)原理及应用场景

文章目录 Jvm基本组成一.什么是JVM类的加载二.类的生命周期阶段1&#xff1a;加载阶段2&#xff1a;验证阶段3&#xff1a;准备阶段4&#xff1a;解析阶段5&#xff1a;初始化 三.类初始化时机四.类加载器1.引导类加载器&#xff08;Bootstrap Class Loader&#xff09;2.拓展类…...

Spring AOP的实现方式

AOP基本概念 Spring框架的两大核心&#xff1a;IoC和AOP AOP&#xff1a;Aspect Oriented Programming&#xff08;面向切面编程&#xff09; AOP是一种思想&#xff0c;是对某一类事情的集中处理 面向切面编程&#xff1a;切面就是指某一类特定的问题&#xff0c;所以AOP可…...

Linux------环境变量

目录 前言 一、环境变量 二、添加PATH环境变量 三、HOME环境变量 四、查看所有环境变量 1.指令获取 2.代码获取 2.1 getenv 2.2main函数的第三个参数 2.3 全局变量environ 五、环境变量存放地点 六、添加自命名环境变量 七、系统环境变量具有全局属性 八、环境变…...

计算机视觉所需要的数学基础

计算机视觉领域中使用的数学知识广泛而深入&#xff0c;以下是一些关键知识点及其在计算机视觉中的应用&#xff1a; 线性代数&#xff1a; - 矩阵运算&#xff1a;用于图像的表示和处理&#xff0c;如图像旋转、缩放、裁剪等。 - 向量空间&#xff1a;用于描述图像中的…...

ChatGPT魔法1: 背后的原理

1. AI的三个阶段 1&#xff09; 上世纪50~60年代&#xff0c;计算机刚刚产生 2&#xff09; Machine learning 3&#xff09; Deep learning&#xff0c; 有神经网络&#xff0c; 最有代表性的是ChatGPT, GPT(Generative Pre-Trained Transformer) 2. 深度神经网络 llya Suts…...

【c/c++】获取时间

在一些应用的编写中我们有时候需要用到时间&#xff0c;或者需要一个“锚点”来确定一些数的值。在c/c中有两个用来确定时间的函数&#xff1a;time/gettimeofday 一、time time_t time(time_t *timer);time 函数返回当前时间的时间戳&#xff08;自 1970 年 1 月 1 日以来经…...

uniapp富文本文字长按选中(用于复制,兼容H5、APP、小程序三端)

方案&#xff1a;使用u-parse的selectable属性 <u-parse :selectable"true" :html"content"></u-parse> 注意&#xff1a;u-parse直接使用是不兼容小程序的&#xff0c;需要对u-parse进行改造&#xff1a; 1. 查看u-parse源码发现小程序走到以…...

常见的几种Web安全问题测试简介

Web项目比较常见的安全问题 1.XSS(CrossSite Script)跨站脚本攻击 XSS(CrossSite Script)跨站脚本攻击。它指的是恶意攻击者往Web 页面里插入恶意html代码&#xff0c;当用户浏览该页之时&#xff0c;嵌入其中Web 里面的html 代码会被执行&#xff0c;从而达到恶意用户的特殊…...

linux信号机制[一]

目录 信号量 时序问题 原子性 什么是信号 信号如何产生 引入 信号的处理方法 常见信号 如何理解组合键变成信号呢&#xff1f; 如何理解信号被进程保存以及信号发送的本质&#xff1f; 为什么要有信号 信号怎么用&#xff1f; 样例代码 core文件有什么用呢&#…...

elementui 中el-date-picker 选择年后输出的是Wed Jan 01 2025 00:00:00 GMT+0800 (中国标准时间)

文章目录 问题分析 问题 在使用 el-date-picker 做只选择年份的控制器时&#xff0c;出现如下问题&#xff1a;el-date-picker选择年后输出的是Wed Jan 01 2025 00:00:00 GMT0800 (中国标准时间)&#xff0c;输出了两次如下 分析 在 el-date-picker 中&#xff0c;我们使用…...

Redis 集群(Cluster)

集群概念 Redis 的哨兵模式&#xff0c;提高了系统的可用性&#xff0c;但是正在用来存储数据的还是 master 和 slave 节点&#xff0c;所有的数据都需要存储在单个 master 和 salve 节点中。 如果数据量很大&#xff0c;接近超出了 master / slave 所在机器的物理内存&#…...

260.【华为OD机试真题】信道分配(贪心算法-JavaPythonC++JS实现)

🚀点击这里可直接跳转到本专栏,可查阅顶置最新的华为OD机试宝典~ 本专栏所有题目均包含优质解题思路,高质量解题代码(Java&Python&C++&JS分别实现),详细代码讲解,助你深入学习,深度掌握! 文章目录 一. 题目-信道分配二.解题思路三.题解代码Python题解代码…...

Python打发无聊时光:3.实现简单电路的仿真

看到这个标题肯定有人会问&#xff1a;好好的multisim、 proteus之类的专门电路仿真软件不用&#xff0c;非要写一个简陋的python程序来弄&#xff0c;是不是精神失常了。实际上&#xff0c;我也不知道为什么要这么干&#xff0c;前两篇文章是我实际项目中的一些探索&#xff0…...

MyBatis-Plus:通用分页实体封装

分页查询实体&#xff1a;PageQuery package com.example.demo.demos.model.query;import com.baomidou.mybatisplus.core.metadata.OrderItem; import com.baomidou.mybatisplus.extension.plugins.pagination.Page; import lombok.Data; import org.springframework.util.St…...

从零实现富文本编辑器#5-编辑器选区模型的状态结构表达

先前我们总结了浏览器选区模型的交互策略&#xff0c;并且实现了基本的选区操作&#xff0c;还调研了自绘选区的实现。那么相对的&#xff0c;我们还需要设计编辑器的选区表达&#xff0c;也可以称为模型选区。编辑器中应用变更时的操作范围&#xff0c;就是以模型选区为基准来…...

[10-3]软件I2C读写MPU6050 江协科技学习笔记(16个知识点)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16...

学校时钟系统,标准考场时钟系统,AI亮相2025高考,赛思时钟系统为教育公平筑起“精准防线”

2025年#高考 将在近日拉开帷幕&#xff0c;#AI 监考一度冲上热搜。当AI深度融入高考&#xff0c;#时间同步 不再是辅助功能&#xff0c;而是决定AI监考系统成败的“生命线”。 AI亮相2025高考&#xff0c;40种异常行为0.5秒精准识别 2025年高考即将拉开帷幕&#xff0c;江西、…...

Springboot社区养老保险系统小程序

一、前言 随着我国经济迅速发展&#xff0c;人们对手机的需求越来越大&#xff0c;各种手机软件也都在被广泛应用&#xff0c;但是对于手机进行数据信息管理&#xff0c;对于手机的各种软件也是备受用户的喜爱&#xff0c;社区养老保险系统小程序被用户普遍使用&#xff0c;为方…...

算法笔记2

1.字符串拼接最好用StringBuilder&#xff0c;不用String 2.创建List<>类型的数组并创建内存 List arr[] new ArrayList[26]; Arrays.setAll(arr, i -> new ArrayList<>()); 3.去掉首尾空格...

Mysql中select查询语句的执行过程

目录 1、介绍 1.1、组件介绍 1.2、Sql执行顺序 2、执行流程 2.1. 连接与认证 2.2. 查询缓存 2.3. 语法解析&#xff08;Parser&#xff09; 2.4、执行sql 1. 预处理&#xff08;Preprocessor&#xff09; 2. 查询优化器&#xff08;Optimizer&#xff09; 3. 执行器…...

现有的 Redis 分布式锁库(如 Redisson)提供了哪些便利?

现有的 Redis 分布式锁库&#xff08;如 Redisson&#xff09;相比于开发者自己基于 Redis 命令&#xff08;如 SETNX, EXPIRE, DEL&#xff09;手动实现分布式锁&#xff0c;提供了巨大的便利性和健壮性。主要体现在以下几个方面&#xff1a; 原子性保证 (Atomicity)&#xff…...

解析两阶段提交与三阶段提交的核心差异及MySQL实现方案

引言 在分布式系统的事务处理中&#xff0c;如何保障跨节点数据操作的一致性始终是核心挑战。经典的两阶段提交协议&#xff08;2PC&#xff09;通过准备阶段与提交阶段的协调机制&#xff0c;以同步决策模式确保事务原子性。其改进版本三阶段提交协议&#xff08;3PC&#xf…...

使用python进行图像处理—图像滤波(5)

图像滤波是图像处理中最基本和最重要的操作之一。它的目的是在空间域上修改图像的像素值&#xff0c;以达到平滑&#xff08;去噪&#xff09;、锐化、边缘检测等效果。滤波通常通过卷积操作实现。 5.1卷积(Convolution)原理 卷积是滤波的核心。它是一种数学运算&#xff0c;…...

使用VMware克隆功能快速搭建集群

自己搭建的虚拟机&#xff0c;后续不管是学习java还是大数据&#xff0c;都需要集群&#xff0c;java需要分布式的微服务&#xff0c;大数据Hadoop的计算集群&#xff0c;如果从头开始搭建虚拟机会比较费时费力&#xff0c;这里分享一下如何使用克隆功能快速搭建一个集群 先把…...