【Leetcode】滑动窗口算法-编程苍穹下划破数据暗夜的高效光弧

前言

🌟🌟本期讲解关于滑动窗口问题~~~

🌈感兴趣的小伙伴看一看小编主页:GGBondlctrl-CSDN博客

🔥 你的点赞就是小编不断更新的最大动力                                       

🎆那么废话不多说直接开整吧~~

目录

📚️1.长度最小的子数组

1.1题目描述

1.2题目解析

1.暴力枚举

2.滑动窗口

1.3代码实现

📚️2.无重复字符最长子串

2.1题目描述

2.2题目解析

1.暴力枚举

2.滑动窗口

2.3代码实现

📚️3.总结


📚️1.长度最小的子数组

1.1题目描述

本题是在一个数组内找到连续且长度最小并且数组内的和大于target数值,题目的描述如下所示:

解释:

此时的要求就是在一个数组内,找到连续的子数组(长度最小,元素的和大于目标数值),那么此时就是返回这里的最小长度即可;

1.2题目解析

1.暴力枚举

具体的思路就是:

第一步:定义两个指针(这两个指针就是表示的左右子数组的边界),然后两个指针的初始位置都是0;

第二步:将这里的right指针向每次后移动一个单位后,进行判断是否大于这里目标值

第三步:判断是否大于这里的值后,若大于则更新我们需要的两个指针之间的长度,若小于就继续向后进行移动;(每一次更新要进行取最小值

第四步:最后进行循环的跳出,边界的判定的操作,最后返回最终的长度

效果如下图所示:

解释:

这就是第一次循环,left不变,然后right不断向后移动,时刻更新这里的len长度,最后知道出界,然后进入外部循环;

解释:此时就是进入外部循环,然后right与left同一个索引的位置;

注意:更新我们需要的长度的时候要注意,这里的两个边界里的元素的和是否大于或等于我们需要的目标值,并且每次更新要取最小的一个长度,这里设计大小比较;

2.滑动窗口

这里的滑动窗口的概念其实就是双指针,并且对于上面的暴力枚举进行了优化的操作,那么具体的思路就是如下所示:

在暴力枚举的操作的情况下,我们发现当子数组内的元素之和已经大于了目标值了,那么此时right就不用向后面走了(因为后面再加肯定大于目标值,但是长度一直在增加,但是这里要最小的),然后left就可以向前走了,若此时数据变小right继续往后面走,此时就会发现,right和left两个指针一直前进;

此时两者都往前面进行移动,包含的元素,然后就像一个窗口向后面滑动一致;所以叫“滑动窗口

具体的画面如下:

解释:

为啥大于目标值right不更新位置:因为right在满足条件后, right再往后移动,确实是满足大于target的条件,但是我们这里的求最小的长度,后面就是无效遍历;

为啥小于目标值left不更新位置:因为这里的值本来就小于了这里的值,left移动不就更小了吗;

1.3代码实现

具体的代码实现如下所示:

class Solution {public int minSubArrayLen(int target, int[] nums) {// 设置两个指针int left = 0;int right = 0;int sum = 0;int len = nums.length+1;// 开始进行循环for (; right < nums.length; right++) {sum += nums[right];while (sum >= target) {len = Math.min(len,right - left + 1);// 如果此时进行的值大,出窗口sum -= nums[left];left++;}}if(len == nums.length+1){return 0;}else{return len;}}
}

解释:

具体的意思,sum就是代表这里的每一步的和,然后当这里的sum大于目标值后就进行判断更新这里的len的大小(取小的)然后此时left移动后,left和right之间的数值就是sum减去left没移动之前的数;

最后为了出现所有的值都不大于目标值,那么就直接返回0,否则返回我们拿到的len子数组的长度的值即可;

时间复杂度

这里一看就是两个循环,那么时间复杂度就是O(n^2),但是这里的两个指针都往前面移动,且不会回头,那么这里的时间复杂度就是O(N+N),最终的时间复杂度就是O(N)

📚️2.无重复字符最长子串

2.1题目描述

这里的题目要求和上面的几乎是一致的,大致就是找最长的子数组(子数组里没有重复的元素);

题目如下:

实例:

一个数组: a b c a b c b b

输出结果:3

最长子数组:[ a b c ]

解释:和上面的题目基本一致,就是返回找到的最长的子数组,然后返回这个子数组的长度即可

2.2题目解析

1.暴力枚举

还是和上面的几乎是不差的,我们可以将这字符串转化为数组的形式,然后利用模拟hash的方式进行存储字母的个数,然后规定两端的指针,len进行比较,返回最大的长度;

大致的情况如下图:

解释:

就是每个字数粗都进行遍历,发现这里存在了重复的元素,那么len不会进行更改,right走完后,left加一,然后重复上述的操作;

2.滑动窗口

结题思路:

大致就是对上述暴力枚举的提升,当这里发现出现重复的时候,right再向后面移动那么就会一直出现重复的元素,所以此时right向后枚举就是无用的,此时就要left向后移动,直到没有重复的元素,然后right再向后面移动,(要更新符合要求的子数组的长度

如下图所示:

解释:

为啥right不向后面重新枚举,假如此刻重上述中left的位置开始向后面移动,那么这里就是[ b ]       [ b c  ] ,[ b  c   a];哎此时就是不用向后移动的原因,len还是会重1更新成3;所以right不用向后重新遍历枚举;

2.3代码实现

具体的代码如下所示:

class Solution {public int lengthOfLongestSubstring(String s) {char[] arr=s.toCharArray();//hash数组int[] hash=new int[128];int left=0,right=0,len=0;while(right < arr.length){//放到hash表里hash[arr[right]]++;while(hash[arr[right]] > 1){//将数据移出hash表hash[arr[left]]--;left++;}len=Math.max(len,right-left+1);right++;}return len;}
}

解释:

这里就是通过hash表的方式判断元素的数量,(hash是通过索引代表的每个元素,128可以代表所有的元素),然后就是right先移动,判断出现是否重复后,在将left位置元素去掉,然后left向后移动;每次移动要判断是否没有了重复的元素;

当然要注意更新len的长度,但是注意了:“right++,和长度的更新,要注意位置,否则长度会多1”

时间复杂度:和上面时间复杂度是一致的都是O(N);

📚️3.总结

上述的两道题主要概括:

right移动看做是进窗口,left移动是出窗口:其实就是进窗口后判断什么时候出窗口,然后按要求更新出窗口之前的长度,继续进窗口,就是一个循环而已~~·

本期主要讲解了双指针优化,滑动窗口的实现;解决了“长度最小的子数组”“无重复字符最长子串”两题;

第一题:LCR 008. 长度最小的子数组 - 力扣(LeetCode)

第二题:3. 无重复字符的最长子串 - 力扣(LeetCode)

🌅🌅🌅~~~~最后希望与诸君共勉,共同进步!!! 


💪💪💪以上就是本期内容了, 感兴趣的话,就关注小编吧。

                 😊😊  期待你的关注~~~

 

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

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

相关文章

go-zero(十二)消息队列

go zero 消息队列 在微服务架构中&#xff0c;消息队列主要通过异步通信实现服务间的解耦&#xff0c;使得各个服务可以独立发展和扩展。 go-zero中使用的队列组件go-queue&#xff0c;是gozero官方实现的基于Kafka和Beanstalkd 的消息队列框架,我们使用kafka作为演示。 一、…

Django基础之模板

一.前言 前面我们讲了视图&#xff0c;我们今天来讲一下模板&#xff0c;模板其实也就是视图中render返回的html进行的渲染&#xff0c;然后展示到浏览器页面上去&#xff0c;那我们今天就来和大家来说一下模板的基本用法 二.寻找html模板 这个也就是我们前面说了的找html&a…

基于回溯法解决八皇后问题+以位运算方法优化n皇后问题(算法与数据结构期末设计)

文章目录 基于回溯法解决八皇后问题以位运算方法优化n皇后问题1. 八皇后问题问题描述2.回溯法求八皇后&#xff08;n皇后&#xff09;问题①由四皇后问题引入②皇后的占位问题③皇后的放置过程④放置过程中的问题⑤回溯算法核心⑥回溯算法的求解过程⑦验证算法和代码实现LeetCo…

Linux - MySQL迁移至一主一从

Linux - MySQL迁移至一主一从 迁移准备安装MySQL ibd文件迁移原服务器操作目标服务器操作 一主一从增量同步异常解决结尾 首先部分单独安装MySQL&#xff0c;请参考Linux - MySQL安装&#xff0c;迁移数据量比较大约400G左右且网络不通故使用文件迁移&#xff0c;需开启一段时间…

PaddleOCR模型ch_PP-OCRv3文本检测模型研究(一)骨干网络

从源码上看&#xff0c;PaddleOCR一共支持四个版本&#xff0c;分别是PP-OCR、PP-OCRv2、PP-OCRv3、PP-OCRv4。本文选择PaddleOCR的v3版本的骨干网络作为研究对象&#xff0c;力图探究网络模型的内部结构。 文章目录 研究起点卷归层压发层残差层骨干网代码实验小结 研究起点 参…

数据结构——栈的模拟实现

大家好&#xff0c;今天我要介绍一下数据结构中的一个经典结构——栈。 一&#xff1a;栈的介绍 与顺序表和单链表不同的是&#xff1a; 顺序表和单链表都可以在头部和尾部插入和删除数据&#xff0c;但是栈的结构就锁死了&#xff08;栈的底部是堵死的&#xff09;栈只能从…

Ubuntu 安装 Samba Server

在 Mac 上如何能够与Ubuntu 服务器共享文件夹&#xff0c;需要在 Ubuntu 上安装 Samba 文件服务器。本文将介绍如何在 Ubuntu 上安装 Samba 服务器从而达到以下目的&#xff1a; Mac 与 Ubuntu 共享文件通过用户名密码访问 安装 Samba 服务 sudo apt install samba修改配置文…

Alan Chhabra:MongoDB AI应用程序计划(MAAP) 为客户提供价值

MongoDB全球合作伙伴执行副总裁 Alan Chhabra 每当有人向我问询MongoDB&#xff0c;我都会说他们很可能在不觉之间已经与MongoDB有过交集。事实上&#xff0c;包括70%财富百强在内的许多世界领先企业公司都在使用MongoDB。我们在MongoDB所做的一切都是为了服务客户&#xff0c…

计算机组成原理与系统结构——微程序控制

笔记内容及图片整理自XJTUSE “计算机组成原理与系统结构” 课程ppt&#xff0c;仅供学习交流使用&#xff0c;谢谢。 基本概念 微指令 将控制单元实现为基本逻辑单元之间的互连并非易事&#xff0c;且设计相对呆板&#xff0c;难以灵活地改变&#xff0c;因此实现微程序控制…

CUDA算子手撕与面试指南

引言 最近秋招落幕&#xff0c;期间一直在找高性能计算&#xff08;HPC&#xff09;相关岗位&#xff0c;整理了一些CUDA算子手撕的代码和知识点分享给大家。 项目地址&#xff1a;https://github.com/Tongkaio/CUDA_Kernel_Samples 如果觉得本项目对你有帮助&#xff0c;欢…

IIS部署程序https是访问出现403或ERR_HTTP2_PROTOCOL_ERROR

一、说明 在windows server 2016中的IIS程序池里部署一套系统&#xff0c;通过https访问站点&#xff0c;同时考虑到安全问题以及防攻击等行为&#xff0c;就用上了WAF云盾功能&#xff0c;能有效的抵挡部分攻击&#xff0c;加强网站的安全性和健壮性。 应用系统一直能够正常…

【EthIf-05】 Ethernet Interface main function

Ethernet Interface main function函数有以下功能和要点&#xff1a; 要实现支持轮询模式下帧传输确认和帧接收的以太网接口轮询机制&#xff1a;实现轮询功能&#xff0c;定期检查传入的帧。帧传输确认&#xff1a;包括确认帧已成功传输的机制。可配置轮询周期&#xff1a;允…

康耐视智能相机(Insight)通过ModbusTCP发送字符串到倍福(BECKHOFF)PLC中

文章目录 1.背景2.分析3.实现3.1.PLC的ModbusTCP_Server3.1.1.安装TF6250-Modbus-TCP3.1.2.PLC设置 3.2.智能相机的ModbusTCP_Client3.2.1.了解ModbusTCP的协议3.2.2.根据协议写代码3.2.2.1.纯函数代码3.2.2.2.脚本代码 3.2.3.非脚本处理时的代码逻辑图3.2.4.关于代码的问题及解…

ruoyi Cannot find module ‘@/views/system/user/index‘

Cannot find module /views/system/user/index 删除node_module 后打包成功

如何将你的 Ruby 应用程序从 OpenSearch 迁移到 Elasticsearch

作者&#xff1a;来自 Elastic Fernando Briano 将 Ruby 代码库从 OpenSearch 客户端迁移到 Elasticsearch 客户端的指南。 OpenSearch Ruby 客户端是从 7.x 版 Elasticsearch Ruby 客户端分叉而来的&#xff0c;因此代码库相对相似。这意味着当将 Ruby 代码库从 OpenSearch 迁…

spring cloud contract http实例

微服务很多时&#xff0c;服务之前相互调用&#xff0c;接口参数的一致性要变得很难维护。 spring cloud contract 提供了测试接口一致性的方法。 一 项目配置 plugins {id "groovy"id "org.springframework.cloud.contract" version "4.0.5"i…

帆软的无数据展示方案

文章目录 需求描述第一步、设置控件第二步、设置数据集优化改进 在日常工作中&#xff0c;使用到帆软报表工具&#xff0c;以下记录日常使用的过程&#xff0c; 需求描述 用帆软报表展示销量的信息&#xff0c;选择不同的订单状态&#xff0c;展示其订单数和总金额。 第一步、…

【操作系统】实验九:设备驱动程序

实验9 设备驱动程序 在钻研Linux内核的人当中&#xff0c;大多数人都是在写设备驱动程序。尽管由于设备的特殊性&#xff0c;使得每个驱动程序都不一样。但是编写设备驱动程序的许多原则和基本技巧都是一样的&#xff0c;甚至Windows下的设备驱动程序从原理上讲也与之相通。在…

文件上传—阿里云OSS对象存储

目录 一、OSS简介 二、OSS基本使用 1. 注册账号 2. 基本配置 (1) 开通OSS (2) 创建存储空间 (3) 修改权限 (4) 配置完成&#xff0c;上传一张图片&#xff0c;检验是否成功。 (5) 创建AccessKey 三、Java项目集成OSS 1. 导入依赖 2. Result.java代码&#xff1a; …

极米投影仪-看电视

文章目录 前言操作步骤1.进入GitHub下载软件2.修改后缀3.粘贴到U盘 前言 使用网络提供的电视接口免费看电视。 操作步骤 1.进入GitHub下载软件 地址&#xff1a;https://github.com/andandroidor/ourtv 也可以直接下载我已保存的apk&#xff0c;地址&#xff1a;https://d…