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

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, 代码 前言 各位读者好, 我是小陈, 这是我的个人主页, 希望我的专栏能够帮助到你: &#x1f4d5; JavaSE基础: 基础语法, 类和对象, 封装继承多态, 接口, 综合小练习图书管理系统等 &#x1f4d7; Java数据结构: 顺序表, 链…...

学习哈哈哈哈

# 零、学习计划 * 数据库相关 * 索引 * [我以为我对数据库索引很了解&#xff0c;直到我遇到了阿里面试官 - 知乎 (zhihu.com)](https://zhuanlan.zhihu.com/p/107487215) * [给我一分钟&#xff0c;让你彻底明白MySQL聚簇索引和非聚簇索引 - 知乎 (zhihu.com)](ht…...

05-基础例程5

基础例程5 1、超声波测距 实验介绍 ​ HC-SR04超声波传感器是一款测量距离的传感器。其原理是利用声波在遇到障碍物反射接收结合声波在空气中传播的速度计算的得出。 外观 管脚功能的定义 VCC&#xff1a;供电电源&#xff1b;Trig&#xff1a;触发信号&#xff1b;Echo&a…...

双基证券:预计未来还会有更多政策来吸引增量资金

双基证券表示&#xff0c;8月27日&#xff0c;活泼资本商场五大方针出台&#xff1a;证券交易印花税折半征收&#xff1b;阶段性收紧IPO节奏&#xff1b;上市房企再融资不受破发、破净和亏本限制&#xff1b;标准控股股东与实际操控人减持行为&#xff1b;融资保证金最低份额由…...

前端: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&#xff0c;打开Jupyter之后是默认在C盘的一个路径的&#xff0c;现在我们就来修改一下它的一个默认打开路径&#xff0c;这样在我们后续学习过程中&#xff0c;可以将ipynb后缀的文件放在这个目录下就能查看了。 1、先打开Anaconda Prompt&#x…...

经典卷积网络

目录 一、经典神经网络出现的时间线​编辑 二、LeNet 三、AlexNet 四、VGGNet 五、InceptionNet 六、ResNet 总结&#xff1a; 一、经典神经网络出现的时间线 二、LeNet 背景&#xff1a;LeNet由Yann LeCun于1998年提出&#xff0c;卷积网络开篇之作。 解释&#xff1…...

react+koa+vite前后端模拟jwt鉴权过程

路由组件&#xff08;生成token&#xff09; 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、数显驱动芯片、数码管驱动芯片

产品品牌&#xff1a;永嘉微电/VINKA 产品型号&#xff1a;VK1616 封装形式&#xff1a;SOP16 产品年份&#xff1a;新年份 概述&#xff1a;VK1616是一种数码管或点阵LED驱动控制专用芯片&#xff0c;内部集成有3线串行接口、数据锁存器、LED 驱动等电路。SEG脚接LED阳极&a…...

开箱报告,Simulink Toolbox库模块使用指南(五)——S-Fuction模块(C MEX S-Function)

文章目录 前言 C MEX S-Function 算法原理 原始信号创建 编写S函数 仿真验证 Tips 分析和应用 总结 前言 见《开箱报告&#xff0c;Simulink Toolbox库模块使用指南&#xff08;一&#xff09;——powergui模块》 见《开箱报告&#xff0c;Simulink Toolbox库模块使用…...

摄像头的调用和视频识别

CV_tutorial3 摄像头调用实时播放保存视频 运动目标识别帧差法背景减除法 摄像头调用 创建视频捕捉对象&#xff1a;cv2.VideoCapture() 参数为视频设备的索引号&#xff0c;就一个摄像投的话写0默认&#xff1b; 或者是指定要读取视频的路径。 实时播放 import cv2 import …...

多通道分离与合并

目录 1.多通道分离split() 2.多通道合并merge() 3.Android JNI demo 1.多通道分离split() void cv::split ( InputArray m, OutputArrayOfArrays mv &#xff09; m:待分离的多通道图像。 mv:分离后的单通道图像&#xff0c;为向量vector形式。 2.多通道合并merge…...

JOJO的奇妙冒险

JOJO,我不想再做人了。 推荐一部动漫 JOJO的奇妙冒险 荒木飞吕彦创作的漫画 《JOJO的奇妙冒险》是由日本漫画家荒木飞吕彦所著漫画。漫画于1987年至2004年在集英社的少年漫画杂志少年JUMP上连载&#xff08;1987年12号刊-2004年47号刊&#xff09;&#xff0c;2005年后在集英…...

LeetCode56.合并区间

这道题我想了一会儿&#xff0c;实在想不到比较好的算法&#xff0c;只能硬着头皮写了&#xff0c;然后不断的debug&#xff0c;经过我不懈的努力&#xff0c;最后还是AC&#xff0c;不过效率确实低。 我就是按照最直接的方法来&#xff0c;先把intervals数组按照第一个数star…...

【内推码:NTAMW6c】 MAXIEYE智驾科技2024校招启动啦

MAXIEYE智驾科技2024校招启动啦【内推码&#xff1a;NTAMW6c】 【招聘岗位超多&#xff01;&#xff01;公司食堂好吃&#xff01;&#xff01;】 算法类&#xff1a;感知算法工程师、SLAM算法工程师、规划控制算法工程师、目标及控制算法工程师、后处理算法工程师 软件类&a…...

Python框架【模板继承 、继承模板实战、类视图 、类视图的好处 、类视图使用场景、基于调度方法的类视图】(四)

&#x1f44f;作者简介&#xff1a;大家好&#xff0c;我是爱敲代码的小王&#xff0c;CSDN博客博主,Python小白 &#x1f4d5;系列专栏&#xff1a;python入门到实战、Python爬虫开发、Python办公自动化、Python数据分析、Python前后端开发 &#x1f4e7;如果文章知识点有错误…...

对于前端模块化的理解与总结(很全乎)

目录 模块化的好处 模块化的commonJS导入导出 暴露(导出)模块&#xff1a;module.exports value或exports.xxx value 导入模块——使用 es6模块化 方法一逐个导出 方法二默认导出 方法三 方法四 方法五 export 和import 同时存在 多个文件导出到一个文件后在相关文件…...

NewStarCTF 2022 web方向题解 wp

----------WEEK1---------- BUU NewStarCTF 公开赛赛道 WEEK1 [NotPHP] 先看题目&#xff0c;要传参加绕过。 分析一下代码&#xff1a;首先get一个datadata://test/plain,Wel…。然后key1和2用数组可以绕过。num2077a可以绕过弱类型。eval()中的php语句被#注释了&#xff0c…...

手游刚开服就被攻击怎么办?如何防御DDoS?

开服初期是手游最脆弱的阶段&#xff0c;极易成为DDoS攻击的目标。一旦遭遇攻击&#xff0c;可能导致服务器瘫痪、玩家流失&#xff0c;甚至造成巨大经济损失。本文为开发者提供一套简洁有效的应急与防御方案&#xff0c;帮助快速应对并构建长期防护体系。 一、遭遇攻击的紧急应…...

Java 语言特性(面试系列2)

一、SQL 基础 1. 复杂查询 &#xff08;1&#xff09;连接查询&#xff08;JOIN&#xff09; 内连接&#xff08;INNER JOIN&#xff09;&#xff1a;返回两表匹配的记录。 SELECT e.name, d.dept_name FROM employees e INNER JOIN departments d ON e.dept_id d.dept_id; 左…...

React第五十七节 Router中RouterProvider使用详解及注意事项

前言 在 React Router v6.4 中&#xff0c;RouterProvider 是一个核心组件&#xff0c;用于提供基于数据路由&#xff08;data routers&#xff09;的新型路由方案。 它替代了传统的 <BrowserRouter>&#xff0c;支持更强大的数据加载和操作功能&#xff08;如 loader 和…...

拉力测试cuda pytorch 把 4070显卡拉满

import torch import timedef stress_test_gpu(matrix_size16384, duration300):"""对GPU进行压力测试&#xff0c;通过持续的矩阵乘法来最大化GPU利用率参数:matrix_size: 矩阵维度大小&#xff0c;增大可提高计算复杂度duration: 测试持续时间&#xff08;秒&…...

如何理解 IP 数据报中的 TTL?

目录 前言理解 前言 面试灵魂一问&#xff1a;说说对 IP 数据报中 TTL 的理解&#xff1f;我们都知道&#xff0c;IP 数据报由首部和数据两部分组成&#xff0c;首部又分为两部分&#xff1a;固定部分和可变部分&#xff0c;共占 20 字节&#xff0c;而即将讨论的 TTL 就位于首…...

项目部署到Linux上时遇到的错误(Redis,MySQL,无法正确连接,地址占用问题)

Redis无法正确连接 在运行jar包时出现了这样的错误 查询得知问题核心在于Redis连接失败&#xff0c;具体原因是客户端发送了密码认证请求&#xff0c;但Redis服务器未设置密码 1.为Redis设置密码&#xff08;匹配客户端配置&#xff09; 步骤&#xff1a; 1&#xff09;.修…...

Python 实现 Web 静态服务器(HTTP 协议)

目录 一、在本地启动 HTTP 服务器1. Windows 下安装 node.js1&#xff09;下载安装包2&#xff09;配置环境变量3&#xff09;安装镜像4&#xff09;node.js 的常用命令 2. 安装 http-server 服务3. 使用 http-server 开启服务1&#xff09;使用 http-server2&#xff09;详解 …...

通过MicroSip配置自己的freeswitch服务器进行调试记录

之前用docker安装的freeswitch的&#xff0c;启动是正常的&#xff0c; 但用下面的Microsip连接不上 主要原因有可能一下几个 1、通过下面命令可以看 [rootlocalhost default]# docker exec -it freeswitch fs_cli -x "sofia status profile internal"Name …...

在golang中如何将已安装的依赖降级处理,比如:将 go-ansible/v2@v2.2.0 更换为 go-ansible/@v1.1.7

在 Go 项目中降级 go-ansible 从 v2.2.0 到 v1.1.7 具体步骤&#xff1a; 第一步&#xff1a; 修改 go.mod 文件 // 原 v2 版本声明 require github.com/apenella/go-ansible/v2 v2.2.0 替换为&#xff1a; // 改为 v…...

FTXUI::Dom 模块

DOM 模块定义了分层的 FTXUI::Element 树&#xff0c;可用于构建复杂的终端界面&#xff0c;支持响应终端尺寸变化。 namespace ftxui {...// 定义文档 定义布局盒子 Element document vbox({// 设置文本 设置加粗 设置文本颜色text("The window") | bold | color(…...