LeetCode 取经之路——第三题-无重复长度的最长子串

2023-12-21 15:20

本文主要是介绍LeetCode 取经之路——第三题-无重复长度的最长子串,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

🎉🎉🎉今天给大家分享的是一道滑动窗口的OJ题。

3.无重复长度的最长子串 

😛😛😛希望我的文章能对你有所帮助,有不足的地方还请各位看官多多指教,大家一起学习交流!

动动你们发财的小手,点点关注点点赞!在此谢过啦!哈哈哈!😛😛😛

目录

一、题目解析 

二、源代码 


 

一、题目解析 

这个题目的意思就是: 在给定的字符串里面,找出不重复的字符串的最大长度。

首先想到的肯定是暴力枚举了,即枚举出所有不重复的字符串,然后找出其中长度最大的。这个还是比较容易想到的。如下图所示:从字符串首元素开始枚举,不重复就一直遍历,直到发现有重复元素为止。但是我们看图是肯定知道有重复,但是代码要怎么写呢?这里就需要用到数据结构中的哈希表了,我的思路是:遍历到一个字符就把它放到哈希表里面,然后再取判断当前这个字符的个数是否大于1,如果大于那就保存当前的字符串长度,继续枚举下一个字符。

其次,不知道大家看了上图后,会不会很容易的想到 "滑动窗口" 。上面的解法,时间复杂度是O(N^2),相对来说还是比较高的,我们可以用 "滑动窗口"的思想来解决问题:

同样也是需要用到哈希表,但是这里我们把字符串转成字符数组后,通过字符ASCII码值也可以判断当前字符个数,因为相同的字符ASCII码值肯定相同,所以在"哈希数组"里存储的位置也肯定是一样的。因此不必使用真正的 "哈希表"。大致思路如下:

  • 定义两个指针 left 和 right,初始时都从 0 开始。
  • right 位置的字符存哈希表,再去判断当前字符的个数是否大于1,如果大于1,那就让 left 位置的字符出窗口,然后 left++,直到当前字符个数为1为止。 
  • 每次判断完,更新一下字符串的长度即可。
  • 最后返回更新的字符串的长度。 

 这种解法,我们不必每次发现重复的字符都要从当前字符的下一个开始遍历,这样的遍历方法最后依然会碰到那个重复的字符,比如:

  • 当前 right 位置发现重复字符a

  • 如果此时从 left 的下一个位置遍历

  • 那么无论如何仍然会碰到那个重复字符a: 

 所以,干脆当我们遇到重复字符的时候,更新字符串长度,然后直接让 left 跳过这个重复字符即可。

此时 right 也不用回退回去找 left 去了。

下面的大致的一个执行流程:

二、源代码 

class Solution {public int lengthOfLongestSubstring(String s) {int hash[] = new int[128];char str[] = s.toCharArray();int ret = 0;int left = 0;int right = 0;int n = str.length;while (right < n){hash[str[right]]++;while (hash[str[right]] > 1){hash[str[left]]--;//发现重复字符,出窗口left++;}ret = Math.max(ret,right - left + 1);right++;}return ret;}
}


✨好啦,今天的分享就到这里!

🎉希望各位看官读完文章后,能够有所提升。

✨创作不易,还希望各位大佬支持一下!

👍点赞,你的认可是我创作的动力!

⭐收藏,你的青睐是我努力的方向!

✏️评论:你的意见是我进步的财富!

 

这篇关于LeetCode 取经之路——第三题-无重复长度的最长子串的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/520504

相关文章

MySQL中查找重复值的实现

《MySQL中查找重复值的实现》查找重复值是一项常见需求,比如在数据清理、数据分析、数据质量检查等场景下,我们常常需要找出表中某列或多列的重复值,具有一定的参考价值,感兴趣的可以了解一下... 目录技术背景实现步骤方法一:使用GROUP BY和HAVING子句方法二:仅返回重复值方法三:返回完整记录方法四:

MySQL 获取字符串长度及注意事项

《MySQL获取字符串长度及注意事项》本文通过实例代码给大家介绍MySQL获取字符串长度及注意事项,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录mysql 获取字符串长度详解 核心长度函数对比⚠️ 六大关键注意事项1. 字符编码决定字节长度2

全面解析MySQL索引长度限制问题与解决方案

《全面解析MySQL索引长度限制问题与解决方案》MySQL对索引长度设限是为了保持高效的数据检索性能,这个限制不是MySQL的缺陷,而是数据库设计中的权衡结果,下面我们就来看看如何解决这一问题吧... 目录引言:为什么会有索引键长度问题?一、问题根源深度解析mysql索引长度限制原理实际场景示例二、五大解决

XML重复查询一条Sql语句的解决方法

《XML重复查询一条Sql语句的解决方法》文章分析了XML重复查询与日志失效问题,指出因DTO缺少@Data注解导致日志无法格式化、空指针风险及参数穿透,进而引发性能灾难,解决方案为在Controll... 目录一、核心问题:从SQL重复执行到日志失效二、根因剖析:DTO断裂引发的级联故障三、解决方案:修复

SpringBoot+Redis防止接口重复提交问题

《SpringBoot+Redis防止接口重复提交问题》:本文主要介绍SpringBoot+Redis防止接口重复提交问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不... 目录前言实现思路代码示例测试总结前言在项目的使用使用过程中,经常会出现某些操作在短时间内频繁提交。例

C#之List集合去重复对象的实现方法

《C#之List集合去重复对象的实现方法》:本文主要介绍C#之List集合去重复对象的实现方法,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录C# List集合去重复对象方法1、测试数据2、测试数据3、知识点补充总结C# List集合去重复对象方法1、测试数据

使用C#删除Excel表格中的重复行数据的代码详解

《使用C#删除Excel表格中的重复行数据的代码详解》重复行是指在Excel表格中完全相同的多行数据,删除这些重复行至关重要,因为它们不仅会干扰数据分析,还可能导致错误的决策和结论,所以本文给大家介绍... 目录简介使用工具C# 删除Excel工作表中的重复行语法工作原理实现代码C# 删除指定Excel单元

Java如何用乘号来重复字符串的功能

《Java如何用乘号来重复字符串的功能》:本文主要介绍Java使用乘号来重复字符串的功能,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Java乘号来重复字符串的功能1、利用循环2、使用StringBuilder3、采用 Java 11 引入的String.rep

SQL常用操作精华之复制表、跨库查询、删除重复数据

《SQL常用操作精华之复制表、跨库查询、删除重复数据》:本文主要介绍SQL常用操作精华之复制表、跨库查询、删除重复数据,这些SQL操作涵盖了数据库开发中最常用的技术点,包括表操作、数据查询、数据管... 目录SQL常用操作精华总结表结构与数据操作高级查询技巧SQL常用操作精华总结表结构与数据操作复制表结

Java实现按字节长度截取字符串

《Java实现按字节长度截取字符串》在Java中,由于字符串可能包含多字节字符,直接按字节长度截取可能会导致乱码或截取不准确的问题,下面我们就来看看几种按字节长度截取字符串的方法吧... 目录方法一:使用String的getBytes方法方法二:指定字符编码处理方法三:更精确的字符编码处理使用示例注意事项方