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

无重复字符的最长子串

题目

添加链接描述

给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长度。示例 1:输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。
示例 2:输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。
示例 3:输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。提示:0 <= s.length <= 5 * 104
s 由英文字母、数字、符号和空格组成

滑动窗口+Set

/*** 滑动窗口+Set*/
private static int lengthOfLongestSubstring(String s) {if (s == null) {return 0;}int length = s.length();// 将当前窗口 [left, right) 中字符存储在 HashSet 中Set<Character> characterSet = new HashSet<>(length);int left = 0, right = 0, ans = 0;while(left < length && right < length) {char c = s.charAt(right);if (!characterSet.contains(c)) {// 滑动窗口[left, right)字符没有重复,字符c添加进setcharacterSet.add(c);// 滑动窗口left不动,right右移一位right++;// 更新无重复子串长度ans:滑动窗口[left, right)的长度=right-leftans = Math.max(ans, right-left);} else {// 存在字符重复,说明滑动窗口 [left, right) 中存在与 c 相等的字符// set集合中删除字符串left处的元素,这里无法直接定位到重复字符的下标,需要从left开始删除到重复位置characterSet.remove(s.charAt(left));// 滑动窗口right不动,left右移一位,循环执行到重复元素被删除left++;}}return ans;
}

优化的滑动窗口+HashMap

如果 s[right] 在 [left,right) 范围内有与​ s[k] 重复的字符,不需要逐渐增加 left 。 可以直接跳过 [left,k] 范围内的所有元素,并将 left 变为 k+1

/**
* 滑动窗口+HashMap
*/
private static int lengthOfLongestSubstring2(String s) {if (s == null) {return 0;}int length = s.length();// 将当前窗口 [left, right) 中字符存储在 HashMap 中// key:字符,value:字符下标HashMap<Character, Integer> map = new HashMap<>(length);int ans = 0;for (int left = 0, right = 0; right < length; right++) {// 滑动窗口右指针位置char c = s.charAt(right);// 判断字符c是否出现过Integer index = map.get(c);// 字符c重复,索引index,当前左指针left// 左指针直接跳转到index+1位置,s[index] == s[right]// 但是不能超过当前left,取max(index+1, left)// 0 1 2 3 4 5 6 7 8// a b c d c e b g h//         l   r// 此时 left 索引为 4,right 遍历到 b,b重复,对应索引 1, 此时不能回溯,left不变if (Objects.nonNull(index)) {left = Math.max(index + 1, left);}// 计算当前子串长度ans = Math.max(ans, right-left+1);// 当前字符加入map集合,如果存在就用当前下标right覆盖map.put(c, right);}return ans;
}

相关文章:

无重复字符的最长子串

题目 添加链接描述 给定一个字符串 s &#xff0c;请你找出其中不含有重复字符的 最长子串 的长度。示例 1:输入: s "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc"&#xff0c;所以其长度为 3。 示例 2:输入: s "bbbbb" 输出…...

C语言--输入10个数字,要求输出其中值最大的元素和该数字是第几个数

今天小编带大家了解一下什么是“打擂台”算法。 一.思路分析 可以定义一个数组arr&#xff0c;长度为10&#xff0c;用来存放10个数字&#xff0c;设计一个函数Max&#xff0c;用来求两个数中的较大值&#xff0c; 定义一个临时变量tmparr[0],保存临时最大的值&#xff0c;下标…...

如何做好功能测试,提升测试质量和效率?

要做好功能测试并提升测试质量和效率&#xff0c;可以考虑以下几个方面&#xff1a; 1. 明确测试目标和需求 在开始功能测试之前&#xff0c;首先要明确测试的目标和需求&#xff0c;包括测试的范围、重点、预期结果等。这有助于为测试工作提供清晰的方向和指导。 2. 制定详细…...

高德地图添加信息弹窗,信息弹窗是单独的组件

//弹窗组件 <template><el-card class"box-card" ref"boxCard" v-if"showCard"><div slot"header" class"clearfix"><div class"title">{{ model.pointName }}</div><div class…...

Apache Arrow优点

优点 采用连续的内存布局&#xff0c;在单机计算的时候&#xff0c;对操作系统友好&#xff0c;增加了缓存命中率以及读取数据的效率采用列式存储&#xff0c;在单机计算的时候&#xff0c;可以利用SMID向量化处理&#xff0c;并且增加了查询效率&#xff08;一般查询的时候只…...

【Linux权限:系统中的数字锁与安全之门】

1.Linux下的用户 Linux下有两种用户&#xff1a;超级用户&#xff08;root&#xff09;、普通用户。 超级用户&#xff1a;可以再linux系统下做任何事情&#xff0c;不受限制普通用户&#xff1a;在linux下做有限的事情。超级用户的命令提示符是“#”&#xff0c;普通用户的命令…...

笔记本电脑的麦克风没有声音

笔记本电脑的麦克风没有声音是一个常见的问题&#xff0c;可能是由于以下几个原因导致的&#xff1a; 第一&#xff0c;麦克风没有启用或者被禁用了。在Windows系统中&#xff0c;右键单击任务栏上的音量图标&#xff0c;选择“录音设备”&#xff0c;在弹出窗口中找到麦克风&a…...

20道简单的投资数学逻辑

20道简单的投资数学逻辑 &#xff08;非常好&#xff0c;强烈推荐&#xff0c;其中第3、第11的案例太经典了&#xff0c;是我反复给金融研究生讲授分析的案例&#xff09; 1、关于收益率 假如你有100万&#xff0c;收益100%后资产达到200万&#xff0c;如果接下来亏损50%&am…...

【Spring】事务实现原理

在使用事务的时候需要添加EnableTransactionManagement注解来开启事务&#xff0c;Spring事务底层是通过AOP来实现的&#xff0c;所以启用事务后&#xff0c;同样会向容器中注入一个代理对象创建器&#xff0c;AOP使用的是AnnotationAwareAspectJAutoProxyCreator&#xff0c;事…...

人工智能基础_机器学习024_梯度下降进阶_L1正则可视化图形---人工智能工作笔记0064

然后我们就来用代码实现一下L1正则的可视化,我们来看看 首先导入 import numpy as np 数学计算 import matplotlib.pyplot as plt 画图用的 然后我们把L1正则的公式写出来 可以看到L1的正则 其实就是w1和w2的绝对值相加对吧 然后这里我们写一个公式: f(x,y) = |x|+|y| …...

媒体聚焦丨四维图新旗下杰发科技王璐:设计决定芯片质量

编者按&#xff1a;新四化、软件定义汽车使汽车芯片成为了最新的半导体增长极&#xff0c;催生了汽车芯片的数量呈倍速增长&#xff0c;汽车芯片功能越来越复杂&#xff0c;迭代速度也越来越快。汽车芯片厂商从最初的设计开始&#xff0c;就要按照车规级芯片的要求对芯片进行全…...

动态规划基础篇(LeetCode每日一题计划)

爬楼梯 求所有爬楼梯的方案 方法一&#xff1a;f(x)f(x-1)f(x-2) class Solution {public int climbStairs(int n) {int p0,q0,r1;for(int i0;i<n;i){pq;qr;rpq;}return r;} } 方法二&#xff1a;动态规划 class Solution { public:int climbStairs(int n) {int dp[46]…...

智慧商业:探索分布式云技术为企业创造商业价值,减少成本,提升生产力的秘诀!

我们可以试想一下&#xff0c;如果没有云计算&#xff0c;商业将会是什么样子&#xff1f; 对于这个问题的答案&#xff0c;许多人会认为它可能依旧是一个以实体为主行业。 云计算和多云战略的出现为在线购物带来了革命性的变化。 然而&#xff0c;如今多云所固有的复杂性仍然…...

Anaconda安装gdal

安装gdal 安装gdal&#xff0c;真是一波三折哇。pip、conda、c编译了等等&#xff0c;网上各种大佬的解决方法都试了试。咱就是说&#xff0c;都不行&#xff0c;很扯淡。甚至 使用conda install gdal 都显示安装成功了&#xff0c;但是 from osgeo import gdal&#xff1b; i…...

vite基础学习笔记:14.路由跳转(二)携带query参数

说明&#xff1a;自学做的笔记和记录&#xff0c;如有错误请指正 1. 路由跳转&#xff08;携带query参数&#xff09; &#xff08;1&#xff09;第一层路由&#xff08;点击卡片路由跳转至新页面-携带query参数&#xff09; 知识点&#xff1a; query传参对应的是path和qu…...

立体相机标定

相机成像过程中涉及的4个坐标系&#xff1a; 1、世界坐标系&#xff1a;由用户定义的三维世界坐标系&#xff0c;描述物体和相机在真实世界中的位置&#xff0c;原点可以任意选择。 2、相机坐标系&#xff1a;以相机的光心为坐标原点&#xff0c;X轴和Y轴平行于图像坐标系的X轴…...

mixin混合类的接口实现

mixin混合类的接口实现 应用 &#xff1a;CreateModelMixin,ListModelMixin,RetrieveModelMixin,DestroyModelMixin,UpdateModelMixin 简化工程代码。 from rest_framework.generics import GenericAPIView from rest_framework.mixins import CreateModelMixin,ListModelMixi…...

前端小技巧: TS实现EventBus自定义事件

关于EventBus事件总线 事件总线&#xff0c;实现 on, once, emit, off on, once 是注册函数&#xff0c;存储起来emit时找到对应的函数&#xff0c;执行off找到对应的函数&#xff0c;从对象中删除 注意 区分on和onceon绑定的事件可连续执行&#xff0c;除非offonce绑定的函数…...

Django之三板斧的使用,全局配置文件介绍,request对象方法,pycharm链接数据库,Django链接数据库,ORM的增删改查

【1】三板斧(3个方法)的使用 Httpresponse() 括号内写什么字符串&#xff0c;返回的就是什么字符串返回的是字符串 render(request&#xff0c; 静态文件 ) request是固定的静态文件是写在templates文件夹里面的&#xff0c;如&#xff0c;HTML文件 redirect( 重定向的地址 ) 重…...

医学影像系统源码(MRI、CT三维重建)

一、MRI概述 核磁共振成像&#xff08;英语&#xff1a;Nuclear Magnetic Resonance Imaging&#xff0c;简称NMRI&#xff09;&#xff0c;又称自旋成像&#xff08;英语&#xff1a;spin imaging&#xff09;&#xff0c;也称磁共振成像&#xff08;Magnetic Resonance Imag…...

VisualCppRedist AIO:一站式解决Windows应用依赖问题的终极指南

VisualCppRedist AIO&#xff1a;一站式解决Windows应用依赖问题的终极指南 【免费下载链接】vcredist AIO Repack for latest Microsoft Visual C Redistributable Runtimes 项目地址: https://gitcode.com/gh_mirrors/vc/vcredist VisualCppRedist AIO是微软Visual C运…...

基于AXI总线的Cortex-M3软核SoC设计与外设集成

1. Cortex-M3软核与AXI总线基础解析 第一次接触Cortex-M3软核是在三年前的一个物联网安全项目&#xff0c;当时需要在FPGA上实现一个轻量级加密处理器。和大多数嵌入式开发者一样&#xff0c;我之前主要使用现成的STM32系列芯片&#xff0c;直到真正动手在Vivado里搭建M3软核&a…...

AI写专著高效之道:AI专著生成工具,20万字专著快速搞定

学术专著写作与AI工具应用 学术专著的主要价值在于其内容的条理清晰和逻辑严谨&#xff0c;但这一点在写作过程中常常是最大的挑战。与专注于单一话题的期刊论文不同&#xff0c;专著的撰写需要构建一个包括绪论、理论基础、核心研究、应用拓展及结论的完整体系。每个章节都应…...

深度解析:SensitivityMatcher如何通过多周期监控算法实现跨游戏鼠标灵敏度精准转换

深度解析&#xff1a;SensitivityMatcher如何通过多周期监控算法实现跨游戏鼠标灵敏度精准转换 【免费下载链接】SensitivityMatcher Script that can be used to convert your mouse sensitivity between different 3D games. 项目地址: https://gitcode.com/gh_mirrors/se/…...

NVIDIA Profile Inspector 2.4.0.1:解锁NVIDIA显卡隐藏性能的终极指南

NVIDIA Profile Inspector 2.4.0.1&#xff1a;解锁NVIDIA显卡隐藏性能的终极指南 【免费下载链接】nvidiaProfileInspector 项目地址: https://gitcode.com/gh_mirrors/nv/nvidiaProfileInspector 你是否曾经觉得NVIDIA显卡的控制面板功能太有限&#xff1f;是否想要更…...

GNU Radio 3.8 OOT模块开发避坑指南:从gr_modtool到CMake编译的完整流程

GNU Radio 3.8 OOT模块开发深度排雷手册&#xff1a;从工具链配置到版本兼容性实战 在软件无线电(SDR)开发领域&#xff0c;GNU Radio作为开源标杆工具链&#xff0c;其Out-of-Tree(OOT)模块扩展机制为开发者提供了高度灵活性。本文将聚焦3.8版本下的OOT开发全流程&#xff0c;…...

STM32H743双FDCAN实战:手把手教你搞定消息RAM分区与过滤表共存(附完整代码)

STM32H743双FDCAN实战&#xff1a;消息RAM分区与过滤表共存深度解析 第一次在H743上同时启用双FDCAN通道时&#xff0c;我遇到了一个诡异现象——CAN1接收的数据偶尔会出现在CAN2的缓冲区里。经过三天调试才发现&#xff0c;问题根源在于那10KB共享消息RAM的配置方式。与传统的…...

共探智能医疗与人工智能的新时代 | IHAI 2026

探索智能医疗与AI的未来 | IHAI 2026 国际会议 地点: 中国玉溪会议简介2026年智能医疗与人工智能国际会议&#xff08;IHAI 2026&#xff09;将于本年度在中国玉溪举行。这座融合了自然美景与多元文化的古城将迎来全球智能医疗和人工智能领域的顶尖专家、学者及行业领袖。本次大…...

基于动态规划的微电网动态经济调度研究附Matlab代码

✅作者简介&#xff1a;热爱科研的Matlab仿真开发者&#xff0c;擅长毕业设计辅导、数学建模、数据处理、建模仿真、程序设计、完整代码获取、论文复现及科研仿真。&#x1f34e; 往期回顾关注个人主页&#xff1a;Matlab科研工作室&#x1f447; 关注我领取海量matlab电子书和…...

Agent 能实现企业 IT 运维流程自动化吗?深度解析2026年AI Agent在运维领域的规模化落地

站在2026年4月的技术节点回望&#xff0c;AI Agent&#xff08;智能体&#xff09;是否能实现企业IT运维流程自动化&#xff0c;已经从一个“技术可行性”的命题&#xff0c;演变为“规模化落地”的行业共识。随着GPT-6的正式发布以及Amazon Agent Registry等全球性智能体注册中…...