当前位置: 首页 > 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…...

分布式风力发电技术与知名厂家情况解析

分布式风力发电作为一种高效、环保的能源获取方式&#xff0c;在当今能源结构中占据着愈发重要的地位。它不仅能有效利用分散的风能资源&#xff0c;减少对传统集中式能源的依赖&#xff0c;还能为偏远地区或小型用电单位提供稳定的电力支持。随着技术的不断进步&#xff0c;分…...

3步打造你的专属影院级播放器:MPV_lazy终极定制指南

3步打造你的专属影院级播放器&#xff1a;MPV_lazy终极定制指南 【免费下载链接】mpv_PlayKit &#x1f504; mpv player 播放器折腾记录 Windows conf | 中文注释配置 汉化文档 快速帮助入门 | mpv-lazy 懒人包 Win11 x64 config | 着色器 shader 滤镜 filter 整合方案 项目…...

智能代码生成覆盖率陷阱全解析,资深SRE亲授覆盖率验证三重校验法与CI/CD嵌入指南

第一章&#xff1a;智能代码生成代码覆盖率分析 2026奇点智能技术大会(https://ml-summit.org) 现代智能代码生成系统&#xff08;如Copilot、CodeWhisperer、Tabnine&#xff09;在提升开发效率的同时&#xff0c;其输出代码的可测试性与结构完整性正成为质量保障的关键挑战…...

STM32项目交付新姿势:用CoFlash把.bin/.elf文件甩给客户,告别源码工程

STM32项目交付新姿势&#xff1a;用CoFlash实现二进制文件的安全传递 在嵌入式开发领域&#xff0c;知识产权保护与高效协作往往是一对难以调和的矛盾。传统开发模式下&#xff0c;工程师不得不将完整的Keil或CubeIDE工程源码打包交付给客户或生产部门&#xff0c;这不仅暴露了…...

保姆级教程:在国产RK3568板卡上从零搭建K3s边缘节点(含国内镜像加速)

国产RK3568板卡实战&#xff1a;从零构建高性能K3s边缘节点全指南 当RK3568遇上K3s&#xff0c;会擦出怎样的火花&#xff1f;这款国产四核ARM处理器以其出色的能效比和丰富的接口资源&#xff0c;正在工业网关、边缘计算盒子等领域大放异彩。而K3s作为CNCF官方认证的轻量级Ku…...

为什么很多企业买了大模型,最后还是落不了地?

很多企业花重金采购了大模型的 API&#xff0c;甚至买了昂贵的算力服务器&#xff0c;满心欢喜地以为迎来了生产力革命&#xff0c;结果三个月后&#xff0c;系统却沦为员工写请假条和废话周报的“高级打字机”。为什么技术如此先进&#xff0c;在企业内部却寸步难行&#xff1…...

别再只删特征了!用Pandas和Seaborn搞定特征共线性,我总结了3种更聪明的处理姿势

特征共线性的高阶处理&#xff1a;从数据删除到信息重构的实战进阶 在房地产价格预测项目中&#xff0c;我们常常遇到一组高度相关的特征——比如白天人口(daypop)、夜间人口(nightpop)和20-39岁夜间人口(night20-39)。传统做法是简单删除"冗余"特征&#xff0c;但这…...

基于cv_resnet101_face-detection_cvpr22papermogface的Java集成实战:SpringBoot服务调用

基于cv_resnet101_face-detection_cvpr22papermogface的Java集成实战&#xff1a;SpringBoot服务调用 想象一下&#xff0c;你正在为一个金融App开发用户实名认证功能&#xff0c;或者为一个社区门禁系统设计人脸通行模块。核心需求很明确&#xff1a;用户上传一张照片&#x…...

SITS2026私有化部署最后窗口期:仅剩62天,官方将于5月31日关闭v1.x License续订通道

第一章&#xff1a;智能代码生成技术&#xff1a;SITS2026开发工具专场 2026奇点智能技术大会(https://ml-summit.org) SITS2026 是面向下一代 AI 原生开发范式的集成式智能工具套件&#xff0c;深度融合大语言模型推理引擎与 IDE 行为感知层&#xff0c;支持上下文感知的实时…...

AI辅助开发术语体系深度剖析

随着生成式AI与软件开发的深度融合&#xff0c;一系列全新的术语和开发范式应运而生。这些概念并非孤立存在&#xff0c;而是相互关联、层层支撑&#xff0c;共同构成了当前AI编程的新骨架。对于有一定基础的开发者而言&#xff0c;系统性掌握这套术语体系&#xff0c;不仅能提…...