Java【手撕滑动窗口】LeetCode 3. “无重复字符的最长子串“, 图文详解思路分析 + 代码
文章目录
- 前言
- 一、长度最小子数组
- 1, 题目
- 2, 思路分析
- 3, 代码
前言
各位读者好, 我是小陈, 这是我的个人主页, 希望我的专栏能够帮助到你:
📕 JavaSE基础: 基础语法, 类和对象, 封装继承多态, 接口, 综合小练习图书管理系统等
📗 Java数据结构: 顺序表, 链表, 堆, 二叉树, 二叉搜索树, 哈希表等
📘 JavaEE初阶: 多线程, 网络编程, TCP/IP协议, HTTP协议, Tomcat, Servlet, Linux, JVM等(正在持续更新)
一、长度最小子数组
1, 题目
OJ链接
一般来说, 如果我们研究的对象是 “连续的区间” 就可以考虑滑动窗口
滑动窗口其实就是"同向双指针", 滑动窗口的特点是, 前后两个指针不会回退, 并且窗口总是向前滑动, 窗口不是固定大小的, 可能边长也可能变短, 如果你在分析题目的时候发现了这些特征, 那就基本是滑动窗口的解法了
2, 思路分析
暴力解法 : 两层 for 循环, 先固定第一个字符, 然后遍历第二个字符, 每遍历到一个字符就判断是否已经出现过, 利用暴力枚举, 寻找出所有子序列
但这一定会超时, 有没有优化的方案呢?
- 1, 使用哈希表, 定义一个 set, 用于检查当前字符是否已经出现过
- 2 , 定义 maxLen, 用于记录目前最大长度
- 3, 定义 left 和 right 指针, 初始位置都从0开始, left 用于标记子序列的左边界, right 用于标记子序列的右边界
前期依然是暴力枚举找到第一个满足条件的子数组, 但接下来就不需要接着暴力枚举, 如图所示

增大窗口对应的操作就是 right++, 缩小窗口的操作就是 left++
right 每指向一个字符, 就判断是否已经存在
- 如果不存在, 直接增大窗口即可
- 如果已经存在, 就 要找到 窗口中的这个已出现的字符, 并将它排除在窗口之外
需要注意的是, " 要找到 窗口中的这个已出现的字符 " 这个操作是一个循环, 但上图中没有表现出来, 如下图所示
综上所述, 可以发现, left 和 right 指针全程没有回退, 并且窗口即会边长也会变短, 但一直在向前滑动, 这就是滑动窗口的特性
3, 代码
public int lengthOfLongestSubstring(String s) {Set<Character> set = new HashSet<>();int left = 0;int right = 0;int maxLen = 0;while(right < s.length()){char ch = s.charAt(right);if(set.contains(ch) ){while(s.charAt(left) != ch) {set.remove(s.charAt(left));left++;}left++;}set.add(ch);maxLen = Math.max(maxLen, right - left + 1);right++;}return maxLen;}
相关文章:
Java【手撕滑动窗口】LeetCode 3. “无重复字符的最长子串“, 图文详解思路分析 + 代码
文章目录 前言一、长度最小子数组1, 题目2, 思路分析3, 代码 前言 各位读者好, 我是小陈, 这是我的个人主页, 希望我的专栏能够帮助到你: 📕 JavaSE基础: 基础语法, 类和对象, 封装继承多态, 接口, 综合小练习图书管理系统等 📗 Java数据结构: 顺序表, 链…...
学习哈哈哈哈
# 零、学习计划 * 数据库相关 * 索引 * [我以为我对数据库索引很了解,直到我遇到了阿里面试官 - 知乎 (zhihu.com)](https://zhuanlan.zhihu.com/p/107487215) * [给我一分钟,让你彻底明白MySQL聚簇索引和非聚簇索引 - 知乎 (zhihu.com)](ht…...
05-基础例程5
基础例程5 1、超声波测距 实验介绍 HC-SR04超声波传感器是一款测量距离的传感器。其原理是利用声波在遇到障碍物反射接收结合声波在空气中传播的速度计算的得出。 外观 管脚功能的定义 VCC:供电电源;Trig:触发信号;Echo&a…...
双基证券:预计未来还会有更多政策来吸引增量资金
双基证券表示,8月27日,活泼资本商场五大方针出台:证券交易印花税折半征收;阶段性收紧IPO节奏;上市房企再融资不受破发、破净和亏本限制;标准控股股东与实际操控人减持行为;融资保证金最低份额由…...
前端:html实现页面切换、顶部标签栏,类似于浏览器的顶部标签栏(完整版)
效果 代码 <!DOCTYPE html> <html><head><style>/* 左侧超链接列表 */.link {display: block;padding: 8px;background-color: #f2f2f2;cursor: pointer;}/* 顶部标签栏 */#tabsContainer {width:98%;display: flex;align-items: center;overflow-x: …...
强化自主可控,润开鸿发布基于RISC-V架构的开源鸿蒙终端新品
2023 RISC-V中国峰会于8月23日至25日在北京召开,峰会以“RISC-V生态共建”为主题,结合当下全球新形势,把握全球新时机,呈现RISC-V全球新观点、新趋势。本次大会邀请了RISC-V国际基金会、业界专家、企业代表及社区伙伴等共同探讨RISC-V发展趋势与机遇,吸引超过百余家业界企业、高…...
软件设计师知识点·1
控制器: (1)指令寄存器(IR) : CPU执行一条指令时,从内存储器取到缓冲寄存器中,再送入IR暂存; (2)程序计数器(PC): 将要执行的下一条指令的地址; (3)地址寄存器(IR): 当前CPU所访问的内存单元地址; (4)指令译码器(ID): 对指令中的操作码字段进行分析解释; 多核CPU可以满足用户…...
修改Jupyter Notebook默认打开路径
这里我是重新下载的anaconda,打开Jupyter之后是默认在C盘的一个路径的,现在我们就来修改一下它的一个默认打开路径,这样在我们后续学习过程中,可以将ipynb后缀的文件放在这个目录下就能查看了。 1、先打开Anaconda Prompt&#x…...
经典卷积网络
目录 一、经典神经网络出现的时间线编辑 二、LeNet 三、AlexNet 四、VGGNet 五、InceptionNet 六、ResNet 总结: 一、经典神经网络出现的时间线 二、LeNet 背景:LeNet由Yann LeCun于1998年提出,卷积网络开篇之作。 解释࿱…...
react+koa+vite前后端模拟jwt鉴权过程
路由组件(生成token) const Router require(koa/router) const jwt require(jsonwebtoken); const router new Router()const mockDbUserInfo [{nickname: xxxliu,username: Tom,password: 123456,icon: url1},{nickname: xxx,username: John,passw…...
VK1616是LED显示控制驱动电路/LED驱动IC、数显驱动芯片、数码管驱动芯片
产品品牌:永嘉微电/VINKA 产品型号:VK1616 封装形式:SOP16 产品年份:新年份 概述:VK1616是一种数码管或点阵LED驱动控制专用芯片,内部集成有3线串行接口、数据锁存器、LED 驱动等电路。SEG脚接LED阳极&a…...
开箱报告,Simulink Toolbox库模块使用指南(五)——S-Fuction模块(C MEX S-Function)
文章目录 前言 C MEX S-Function 算法原理 原始信号创建 编写S函数 仿真验证 Tips 分析和应用 总结 前言 见《开箱报告,Simulink Toolbox库模块使用指南(一)——powergui模块》 见《开箱报告,Simulink Toolbox库模块使用…...
摄像头的调用和视频识别
CV_tutorial3 摄像头调用实时播放保存视频 运动目标识别帧差法背景减除法 摄像头调用 创建视频捕捉对象:cv2.VideoCapture() 参数为视频设备的索引号,就一个摄像投的话写0默认; 或者是指定要读取视频的路径。 实时播放 import cv2 import …...
多通道分离与合并
目录 1.多通道分离split() 2.多通道合并merge() 3.Android JNI demo 1.多通道分离split() void cv::split ( InputArray m, OutputArrayOfArrays mv ) m:待分离的多通道图像。 mv:分离后的单通道图像,为向量vector形式。 2.多通道合并merge…...
JOJO的奇妙冒险
JOJO,我不想再做人了。 推荐一部动漫 JOJO的奇妙冒险 荒木飞吕彦创作的漫画 《JOJO的奇妙冒险》是由日本漫画家荒木飞吕彦所著漫画。漫画于1987年至2004年在集英社的少年漫画杂志少年JUMP上连载(1987年12号刊-2004年47号刊),2005年后在集英…...
LeetCode56.合并区间
这道题我想了一会儿,实在想不到比较好的算法,只能硬着头皮写了,然后不断的debug,经过我不懈的努力,最后还是AC,不过效率确实低。 我就是按照最直接的方法来,先把intervals数组按照第一个数star…...
【内推码:NTAMW6c】 MAXIEYE智驾科技2024校招启动啦
MAXIEYE智驾科技2024校招启动啦【内推码:NTAMW6c】 【招聘岗位超多!!公司食堂好吃!!】 算法类:感知算法工程师、SLAM算法工程师、规划控制算法工程师、目标及控制算法工程师、后处理算法工程师 软件类&a…...
Python框架【模板继承 、继承模板实战、类视图 、类视图的好处 、类视图使用场景、基于调度方法的类视图】(四)
👏作者简介:大家好,我是爱敲代码的小王,CSDN博客博主,Python小白 📕系列专栏:python入门到实战、Python爬虫开发、Python办公自动化、Python数据分析、Python前后端开发 📧如果文章知识点有错误…...
对于前端模块化的理解与总结(很全乎)
目录 模块化的好处 模块化的commonJS导入导出 暴露(导出)模块:module.exports value或exports.xxx value 导入模块——使用 es6模块化 方法一逐个导出 方法二默认导出 方法三 方法四 方法五 export 和import 同时存在 多个文件导出到一个文件后在相关文件…...
NewStarCTF 2022 web方向题解 wp
----------WEEK1---------- BUU NewStarCTF 公开赛赛道 WEEK1 [NotPHP] 先看题目,要传参加绕过。 分析一下代码:首先get一个datadata://test/plain,Wel…。然后key1和2用数组可以绕过。num2077a可以绕过弱类型。eval()中的php语句被#注释了,…...
【JavaEE】-- HTTP
1. HTTP是什么? HTTP(全称为"超文本传输协议")是一种应用非常广泛的应用层协议,HTTP是基于TCP协议的一种应用层协议。 应用层协议:是计算机网络协议栈中最高层的协议,它定义了运行在不同主机上…...
【Linux】C语言执行shell指令
在C语言中执行Shell指令 在C语言中,有几种方法可以执行Shell指令: 1. 使用system()函数 这是最简单的方法,包含在stdlib.h头文件中: #include <stdlib.h>int main() {system("ls -l"); // 执行ls -l命令retu…...
【CSS position 属性】static、relative、fixed、absolute 、sticky详细介绍,多层嵌套定位示例
文章目录 ★ position 的五种类型及基本用法 ★ 一、position 属性概述 二、position 的五种类型详解(初学者版) 1. static(默认值) 2. relative(相对定位) 3. absolute(绝对定位) 4. fixed(固定定位) 5. sticky(粘性定位) 三、定位元素的层级关系(z-i…...
QT: `long long` 类型转换为 `QString` 2025.6.5
在 Qt 中,将 long long 类型转换为 QString 可以通过以下两种常用方法实现: 方法 1:使用 QString::number() 直接调用 QString 的静态方法 number(),将数值转换为字符串: long long value 1234567890123456789LL; …...
聊一聊接口测试的意义有哪些?
目录 一、隔离性 & 早期测试 二、保障系统集成质量 三、验证业务逻辑的核心层 四、提升测试效率与覆盖度 五、系统稳定性的守护者 六、驱动团队协作与契约管理 七、性能与扩展性的前置评估 八、持续交付的核心支撑 接口测试的意义可以从四个维度展开,首…...
MySQL账号权限管理指南:安全创建账户与精细授权技巧
在MySQL数据库管理中,合理创建用户账号并分配精确权限是保障数据安全的核心环节。直接使用root账号进行所有操作不仅危险且难以审计操作行为。今天我们来全面解析MySQL账号创建与权限分配的专业方法。 一、为何需要创建独立账号? 最小权限原则…...
Unsafe Fileupload篇补充-木马的详细教程与木马分享(中国蚁剑方式)
在之前的皮卡丘靶场第九期Unsafe Fileupload篇中我们学习了木马的原理并且学了一个简单的木马文件 本期内容是为了更好的为大家解释木马(服务器方面的)的原理,连接,以及各种木马及连接工具的分享 文件木马:https://w…...
服务器--宝塔命令
一、宝塔面板安装命令 ⚠️ 必须使用 root 用户 或 sudo 权限执行! sudo su - 1. CentOS 系统: yum install -y wget && wget -O install.sh http://download.bt.cn/install/install_6.0.sh && sh install.sh2. Ubuntu / Debian 系统…...
HarmonyOS运动开发:如何用mpchart绘制运动配速图表
##鸿蒙核心技术##运动开发##Sensor Service Kit(传感器服务)# 前言 在运动类应用中,运动数据的可视化是提升用户体验的重要环节。通过直观的图表展示运动过程中的关键数据,如配速、距离、卡路里消耗等,用户可以更清晰…...
保姆级教程:在无网络无显卡的Windows电脑的vscode本地部署deepseek
文章目录 1 前言2 部署流程2.1 准备工作2.2 Ollama2.2.1 使用有网络的电脑下载Ollama2.2.2 安装Ollama(有网络的电脑)2.2.3 安装Ollama(无网络的电脑)2.2.4 安装验证2.2.5 修改大模型安装位置2.2.6 下载Deepseek模型 2.3 将deepse…...
