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

无重复字符的最长子串 - 力扣(LeetCode)

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

给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。

示例 2:

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。

示例 3:

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。

1、将字符串分为两个集合,第一个集合是目前最长串,第二个集合是需要加入最长串的字符

每次从第二个集合拿一个字符串,判读是否第一个集合存在该字符串

开始     NULL      S{abcabcbb}    

             {a}   {bcabcbb}    //加入第一个结合

            {ab}   {cabcbb}   

           {abc}  {abcbb}

           {bca}   {bcbb}     //重复了,需要调整第一个字符串

..... 直到第二个字符串为空

    public int lengthOfLongestSubstring(String s) {if(s==null || s.length()==0) return 0;int len = s.length();int left=0,right=0,max=1;for(int i=1;i<len;i++){boolean find = false;for(int j=left;j<=right;j++){if(s.charAt(j)==s.charAt(i)){left=j+1;right=i;find=true;if(right-left+1>max)max=right-left+1;break;}}if(find == false){right=i;if(right-left+1>max)max=right-left+1;}}return max;}

将for 循环替换为java 字符串函数

public static int lengthOfLongestSubstring(String s) {if(s==null || s.length()==0) return 0;int len = s.length();int left=0,right=0,max=1;for(int i=1;i<len;i++){String src=s.subSequence(left,right+1).toString();int offset = src.indexOf(s.charAt(i));if(offset != -1){left+=offset+1;right=i;if(right-left+1>max)max=right-left+1;continue;}right = i;if (right - left + 1 > max)max = right - left + 1;}return max;}

方法一:滑动窗口
思路和算法

我们先用一个例子考虑如何在较优的时间复杂度内通过本题。

我们不妨以示例一中的字符串 abcabcbb\texttt{abcabcbb}abcabcbb 为例,找出从每一个字符开始的,不包含重复字符的最长子串,那么其中最长的那个字符串即为答案。对于示例一中的字符串,我们列举出这些结果,其中括号中表示选中的字符以及最长的字符串:

以 (a)bcabcbb\texttt{(a)bcabcbb}(a)bcabcbb 开始的最长字符串为 (abc)abcbb\texttt{(abc)abcbb}(abc)abcbb;
以 a(b)cabcbb\texttt{a(b)cabcbb}a(b)cabcbb 开始的最长字符串为 a(bca)bcbb\texttt{a(bca)bcbb}a(bca)bcbb;
以 ab(c)abcbb\texttt{ab(c)abcbb}ab(c)abcbb 开始的最长字符串为 ab(cab)cbb\texttt{ab(cab)cbb}ab(cab)cbb;
以 abc(a)bcbb\texttt{abc(a)bcbb}abc(a)bcbb 开始的最长字符串为 abc(abc)bb\texttt{abc(abc)bb}abc(abc)bb;
以 abca(b)cbb\texttt{abca(b)cbb}abca(b)cbb 开始的最长字符串为 abca(bc)bb\texttt{abca(bc)bb}abca(bc)bb;
以 abcab(c)bb\texttt{abcab(c)bb}abcab(c)bb 开始的最长字符串为 abcab(cb)b\texttt{abcab(cb)b}abcab(cb)b;
以 abcabc(b)b\texttt{abcabc(b)b}abcabc(b)b 开始的最长字符串为 abcabc(b)b\texttt{abcabc(b)b}abcabc(b)b;
以 abcabcb(b)\texttt{abcabcb(b)}abcabcb(b) 开始的最长字符串为 abcabcb(b)\texttt{abcabcb(b)}abcabcb(b)。
发现了什么?如果我们依次递增地枚举子串的起始位置,那么子串的结束位置也是递增的!这里的原因在于,假设我们选择字符串中的第 kkk 个字符作为起始位置,并且得到了不包含重复字符的最长子串的结束位置为 rkr_kr 
k

 。那么当我们选择第 k+1k+1k+1 个字符作为起始位置时,首先从 k+1k+1k+1 到 rkr_kr 
k

  的字符显然是不重复的,并且由于少了原本的第 kkk 个字符,我们可以尝试继续增大 rkr_kr 
k

 ,直到右侧出现了重复字符为止。

这样一来,我们就可以使用「滑动窗口」来解决这个问题了:

我们使用两个指针表示字符串中的某个子串(或窗口)的左右边界,其中左指针代表着上文中「枚举子串的起始位置」,而右指针即为上文中的 rkr_kr 
k

 ;

在每一步的操作中,我们会将左指针向右移动一格,表示 我们开始枚举下一个字符作为起始位置,然后我们可以不断地向右移动右指针,但需要保证这两个指针对应的子串中没有重复的字符。在移动结束后,这个子串就对应着 以左指针开始的,不包含重复字符的最长子串。我们记录下这个子串的长度;

在枚举结束后,我们找到的最长的子串的长度即为答案。

判断重复字符

在上面的流程中,我们还需要使用一种数据结构来判断 是否有重复的字符,常用的数据结构为哈希集合(即 C++ 中的 std::unordered_set,Java 中的 HashSet,Python 中的 set, JavaScript 中的 Set)。在左指针向右移动的时候,我们从哈希集合中移除一个字符,在右指针向右移动的时候,我们往哈希集合中添加一个字符。

至此,我们就完美解决了本题。

作者:力扣官方题解
链接:https://leetcode.cn/problems/longest-substring-without-repeating-characters/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

class Solution {public int lengthOfLongestSubstring(String s) {// 哈希集合,记录每个字符是否出现过Set<Character> occ = new HashSet<Character>();int n = s.length();// 右指针,初始值为 -1,相当于我们在字符串的左边界的左侧,还没有开始移动int rk = -1, ans = 0;for (int i = 0; i < n; ++i) {if (i != 0) {// 左指针向右移动一格,移除一个字符occ.remove(s.charAt(i - 1));}while (rk + 1 < n && !occ.contains(s.charAt(rk + 1))) {// 不断地移动右指针occ.add(s.charAt(rk + 1));++rk;}// 第 i 到 rk 个字符是一个极长的无重复字符子串ans = Math.max(ans, rk - i + 1);}return ans;}
}作者:力扣官方题解
链接:https://leetcode.cn/problems/longest-substring-without-repeating-characters/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

相关文章:

无重复字符的最长子串 - 力扣(LeetCode)

3. 无重复字符的最长子串 - 力扣&#xff08;LeetCode&#xff09; 给定一个字符串 s &#xff0c;请你找出其中不含有重复字符的 最长子串 的长度。 示例 1: 输入: s "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc"&#xff0c;所以其长…...

企业行政许可的种类有哪些?

从行政许可的性质、功能和适用条件的角度来说&#xff0c;大体可以划分为五类&#xff1a;普通许可、特许、认可、核准、登记。 1.普通许可 普通许可是一种允许符合特定条件的相对方行使某种权利的行为。在许多情况下&#xff0c;需要普通许可的活动都与国家安全、公共安全息…...

Flink--4、DateStream API(执行环境、源算子、基本转换算子)

星光下的赶路人star的个人主页 注意力的集中&#xff0c;意象的孤立绝缘&#xff0c;便是美感的态度的最大特点 文章目录 1、DataStream API1.1 执行环境&#xff08;Execution Environment&#xff09;1.1.1 创建执行环境 1.2 执行模式&#xff08;Execution Mode&#xff09;…...

#循循渐进学51单片机#指针基础与1602液晶的初步认识#not.11

1、把本节课的指针相关内容&#xff0c;反复学习3到5遍&#xff0c;彻底弄懂指针是怎么回事&#xff0c;即使是死记硬背也要记住&#xff0c;等到后边用的时候可以实现顿悟。学会指针&#xff0c;就是突破了C语言的一道壁垒。 2&#xff0c;1602所有的指令功能都应用一遍&#…...

Lua学习笔记:探究package

前言 本篇在讲什么 理解Lua的package 本篇需要什么 对Lua语法有简单认知 对C语法有简单认知 依赖Visual Studio工具 本篇的特色 具有全流程的图文教学 重实践&#xff0c;轻理论&#xff0c;快速上手 提供全流程的源码内容 ★提高阅读体验★ &#x1f449; ♠ 一级…...

【面试经典150 | 双指针】三数之和

文章目录 写在前面Tag题目来源题目解读解题思路方法一&#xff1a;暴力枚举方法二&#xff1a;双指针 写在最后 写在前面 本专栏专注于分析与讲解【面试经典150】算法&#xff0c;两到三天更新一篇文章&#xff0c;欢迎催更…… 专栏内容以分析题目为主&#xff0c;并附带一些对…...

现代卷积网络实战系列3:PyTorch从零构建AlexNet训练MNIST数据集

1、AlexNet AlexNet提出了一下5点改进&#xff1a; 使用了Dropout&#xff0c;防止过拟合使用Relu作为激活函数&#xff0c;极大提高了特征提取效果使用MaxPooling池化进行特征降维&#xff0c;极大提高了特征提取效果首次使用GPU进行训练使用了LRN局部响应归一化&#xff08…...

Django系列:Django应用(app)的创建与配置

Django系列 Django应用&#xff08;app&#xff09;的创建与配置 作者&#xff1a;李俊才 &#xff08;jcLee95&#xff09;&#xff1a;https://blog.csdn.net/qq_28550263 邮箱 &#xff1a;291148484163.com 本文地址&#xff1a;https://blog.csdn.net/qq_28550263/article…...

Linux查看程序和动态库依赖的动态库

一. 前言 在一些时候&#xff0c;我们需要知道一个程序或者动态库所依赖的动态库有哪些。比如&#xff0c;当我们运行一个程序的时候&#xff0c;发现可能会报错&#xff0c;提示找不到某个符号&#xff0c;这时我们就需要知道程序依赖了什么库&#xff0c;从而添加对应需要的动…...

vue3 无法使用pnpm安装依赖 或 Cannot find module preinstall.js

创建.npmrc文件在根目录 shamefully-hoisttrue auto-install-peerstrue strict-peer-dependenciesfalse删除 node_modules 和 pnpm-lock.yaml 文件 重新 pnpm i 就可以啦...

C/C++连接数据库,包含完整代码。

C/C连接数据库 本篇文章意在简洁明了的在linux环境下使用C/C连接远程数据库&#xff0c;并对数据库进行增删查改等操作。我所使用的环境是centos7&#xff0c;不要环境除环境配置外&#xff0c;代码是大同小异的。完整代码在最底部&#xff01;&#xff01;&#xff01; 1.前…...

AUTOSAR词典:CAN驱动Mailbox配置技术要点全解析

AUTOSAR词典&#xff1a;CAN驱动Mailbox配置技术要点全解析 前言 首先&#xff0c;请问大家几个小小问题&#xff0c;你清楚&#xff1a; AUTOSAR框架下的CAN驱动关键词定义吗&#xff1f;是不是有些总是傻傻分不清楚呢&#xff1f;CAN驱动Mailbox配置过程中有哪些关键配置参…...

C语言 coding style

头文件 The #define Guard #define的保护文件的唯一性&#xff0c;防止被多重包含 格式 : <PROJECT>_< FILE>_H_ PROJECT : XS FILE : MV_CTR 头文件的包含顺序 C System FilesOther LibrariesUser LibraryConditional include 作用域 局部变量 -变量定义时需要…...

Python办公自动化之PDF

Python操作PDF 1、Python操作PDF概述2、批量拆分3、批量合并4、提取内容(文字)5、提取内容(表格)6、提取图片7、PDF添加水印8、加密与解密1、Python操作PDF概述 Python操作PDF主要有两个库:PyPDF2和pdfplumber PyPDF2是一个用于处理PDF文件的Python第三方库 官网文档参考:…...

【每日一题Day331】LC2560打家劫舍 IV | 二分查找 + 贪心

打家劫舍 IV【LC2560】 沿街有一排连续的房屋。每间房屋内都藏有一定的现金。现在有一位小偷计划从这些房屋中窃取现金。 由于相邻的房屋装有相互连通的防盗系统&#xff0c;所以小偷 不会窃取相邻的房屋 。 小偷的 窃取能力 定义为他在窃取过程中能从单间房屋中窃取的 最大金额…...

JVM 参数详解

GC有两种类型&#xff1a;Scavenge GC 和Full GC 1、Scavenge GC 一般情况下&#xff0c;当新对象生成&#xff0c;并且在Eden申请空间失败时&#xff0c;就会触发Scavenge GC&#xff0c;堆的Eden区域进行GC&#xff0c;清除非存活对象&#xff0c;并且把尚且存活的对象移动到…...

uni-app获取地理位置

在uni-app中&#xff0c;可以通过uni.getLocation()方法获取地理位置。具体步骤如下&#xff1a; 在uni-app项目中的manifest.json文件中&#xff0c;添加需要获取地理位置的权限&#xff1a; {"mp-weixin": {"appid": "...","permission…...

Learn Prompt-Prompt 高级技巧:思维链 Chain of Thought Prompting

Jason Wei等作者对思维链的定义是一系列的中间推理步骤&#xff08; a series of intermediate reasoning steps &#xff09;。目的是为了提高大型语言模型&#xff08;LLM&#xff09;进行复杂推理的能力。 思维链通常是伴随着算术&#xff0c;常识和符号推理等复杂推理任务出…...

Vim编辑器使用入门

目录 一、Vim 编辑器基础操作 二、Vim 编辑器进阶操作 三、Vim 编辑器高级操作 四、Vim 编辑器文件操作 五、Vim 编辑器文件管理 六、Vim 编辑器进阶技巧 七、Vim 编辑器增强功能 Vim的三种工作模式 一、Vim 编辑器基础操作 1.移动光标 - 光标的移动控制 移动光标有两…...

早餐与风景

来吧&#xff0c;我用流水账描述下这一天。 时维九月&#xff0c;北京的早上有点冷&#xff0c;因为今天有个市场活动要去支撑&#xff0c;按照会议时间的要求&#xff0c;我需要在早上7点半就赶到会场&#xff0c;所以昨天晚上我加班到凌晨处理完了今天要给出去的材料&#xf…...

微信小程序之bind和catch

这两个呢&#xff0c;都是绑定事件用的&#xff0c;具体使用有些小区别。 官方文档&#xff1a; 事件冒泡处理不同 bind&#xff1a;绑定的事件会向上冒泡&#xff0c;即触发当前组件的事件后&#xff0c;还会继续触发父组件的相同事件。例如&#xff0c;有一个子视图绑定了b…...

从零实现富文本编辑器#5-编辑器选区模型的状态结构表达

先前我们总结了浏览器选区模型的交互策略&#xff0c;并且实现了基本的选区操作&#xff0c;还调研了自绘选区的实现。那么相对的&#xff0c;我们还需要设计编辑器的选区表达&#xff0c;也可以称为模型选区。编辑器中应用变更时的操作范围&#xff0c;就是以模型选区为基准来…...

【入坑系列】TiDB 强制索引在不同库下不生效问题

文章目录 背景SQL 优化情况线上SQL运行情况分析怀疑1:执行计划绑定问题?尝试:SHOW WARNINGS 查看警告探索 TiDB 的 USE_INDEX 写法Hint 不生效问题排查解决参考背景 项目中使用 TiDB 数据库,并对 SQL 进行优化了,添加了强制索引。 UAT 环境已经生效,但 PROD 环境强制索…...

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

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

高防服务器能够抵御哪些网络攻击呢?

高防服务器作为一种有着高度防御能力的服务器&#xff0c;可以帮助网站应对分布式拒绝服务攻击&#xff0c;有效识别和清理一些恶意的网络流量&#xff0c;为用户提供安全且稳定的网络环境&#xff0c;那么&#xff0c;高防服务器一般都可以抵御哪些网络攻击呢&#xff1f;下面…...

保姆级教程:在无网络无显卡的Windows电脑的vscode本地部署deepseek

文章目录 1 前言2 部署流程2.1 准备工作2.2 Ollama2.2.1 使用有网络的电脑下载Ollama2.2.2 安装Ollama&#xff08;有网络的电脑&#xff09;2.2.3 安装Ollama&#xff08;无网络的电脑&#xff09;2.2.4 安装验证2.2.5 修改大模型安装位置2.2.6 下载Deepseek模型 2.3 将deepse…...

免费PDF转图片工具

免费PDF转图片工具 一款简单易用的PDF转图片工具&#xff0c;可以将PDF文件快速转换为高质量PNG图片。无需安装复杂的软件&#xff0c;也不需要在线上传文件&#xff0c;保护您的隐私。 工具截图 主要特点 &#x1f680; 快速转换&#xff1a;本地转换&#xff0c;无需等待上…...

【JavaSE】多线程基础学习笔记

多线程基础 -线程相关概念 程序&#xff08;Program&#xff09; 是为完成特定任务、用某种语言编写的一组指令的集合简单的说:就是我们写的代码 进程 进程是指运行中的程序&#xff0c;比如我们使用QQ&#xff0c;就启动了一个进程&#xff0c;操作系统就会为该进程分配内存…...

Razor编程中@Html的方法使用大全

文章目录 1. 基础HTML辅助方法1.1 Html.ActionLink()1.2 Html.RouteLink()1.3 Html.Display() / Html.DisplayFor()1.4 Html.Editor() / Html.EditorFor()1.5 Html.Label() / Html.LabelFor()1.6 Html.TextBox() / Html.TextBoxFor() 2. 表单相关辅助方法2.1 Html.BeginForm() …...

淘宝扭蛋机小程序系统开发:打造互动性强的购物平台

淘宝扭蛋机小程序系统的开发&#xff0c;旨在打造一个互动性强的购物平台&#xff0c;让用户在购物的同时&#xff0c;能够享受到更多的乐趣和惊喜。 淘宝扭蛋机小程序系统拥有丰富的互动功能。用户可以通过虚拟摇杆操作扭蛋机&#xff0c;实现旋转、抽拉等动作&#xff0c;增…...