图解LeetCode——剑指 Offer 48. 最长不含重复字符的子字符串

简介: 图解LeetCode——剑指 Offer 48. 最长不含重复字符的子字符串

一、题目

请从字符串中找出一个最长的不包含重复字符的子字符串,计算该最长子字符串的长度。

二、示例

2.1> 示例 1:

【输入】 "abcabcbb"

【输出】 3

【解释】 因为无重复字符的最长子串是 "abc",所以其长度为 3。

2.2> 示例 2:

【输入】 "bbbbb"

【输出】 1

【解释】 因为无重复字符的最长子串是 "b",所以其长度为 1。

2.3> 示例 3:

【输入】 "pwwkew"

【输出】 3

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

提示:

  • s.length <= 40000

三、解题思路

  • 根据题目描述,我们要确保找到的子字符串中不包含重复字符。那么我们创建一个head指针,用于指向子字符串中的第一个字符。
  • 由于需要判断子字符串中是否包含了重复的字符,那么我们就需要一个mark变量,它可以是数组或者哈希表的数据结构,用来保存子字符串中出现过的字符和这个字符的最新下标值,此处需要注意的是,如果使用数组,则初始化一个128长度的int数组即可,因为在ASCII表中,一共记录128个字符。但是如果采用Map则不需要在意容器的初始化大小了。
  • 那么我们从头开始遍历数组s,当遍历到某个字符x发现它在mark中存在(我们用mark[x]表示),那么我们需要做如下判断:

如果mark[x] < head】则表示不重复,因为mark[x]这个下标位置已经在head之前了,即:不包含在当前的子字符串中。

如果mark[x] >= head】则表示发生了字符重复。那么当前这个子字符串就结束了。将head指向mark[x]+1的位置,作为全新的子字符串head指针。并且计算上一个子字符串的长度,如果大于历史最长子串长度,则赋值到result变量中。还有不要忘记了更新字符xmark中的最新下标位置。

  • 这样经过上面的流程遍历完字符串s,最终的result值,就是最长不含重复字符的子字符串。
  • 为了更好理解,我们还是举个例子,即:输入字符串为s="abcbb",那么具体的执行流程请见下图所示:

四、代码实现

classSolution {
publicintlengthOfLongestSubstring(Strings) {
intresult=0, head=0;
char[] sc=s.toCharArray();
int[] mark=newint[128];
Arrays.fill(mark, -1);
for (inti=0; i<sc.length; i++) { 
if (mark[sc[i]] >=head) head=mark[sc[i]] +1;
result=Math.max(result, i-head+1);
mark[sc[i]] =i;     
        }
returnresult;
    }
}

今天的文章内容就这些了:

写作不易,笔者几个小时甚至数天完成的一篇文章,只愿换来您几秒钟的 点赞 & 分享

更多技术干货,欢迎大家关注公众号“爪哇缪斯” ~ \(^o^)/ ~ 「干货分享,每天更新」

相关文章
|
1天前
|
算法 索引 Python
二刷力扣--字符串
二刷力扣--字符串
|
2天前
|
算法 容器
【LeetCode刷题】滑动窗口解决问题:水果成篮、找到字符串中所有字母异位词
【LeetCode刷题】滑动窗口解决问题:水果成篮、找到字符串中所有字母异位词
|
2天前
【LeetCode刷题】滑动窗口思想解决问题:长度最小的子数组、无重复字符的最长子串
【LeetCode刷题】滑动窗口思想解决问题:长度最小的子数组、无重复字符的最长子串
|
2天前
|
算法
【经典LeetCode算法题目专栏分类】【第8期】滑动窗口:最小覆盖子串、字符串排列、找所有字母异位词、 最长无重复子串
【经典LeetCode算法题目专栏分类】【第8期】滑动窗口:最小覆盖子串、字符串排列、找所有字母异位词、 最长无重复子串
|
6天前
|
存储 算法 数据挖掘
深入解析力扣166题:分数到小数(模拟长除法与字符串操作详解及模拟面试问答)
深入解析力扣166题:分数到小数(模拟长除法与字符串操作详解及模拟面试问答)
|
6天前
|
存储 算法 数据可视化
深入解析力扣161题:相隔为 1 的编辑距离(逐字符比较与动态规划详解)
深入解析力扣161题:相隔为 1 的编辑距离(逐字符比较与动态规划详解)
|
6天前
|
存储 算法 数据可视化
深入解析力扣157题:用Read4高效读取N个字符(多种解法与详细图解)
深入解析力扣157题:用Read4高效读取N个字符(多种解法与详细图解)
|
6天前
|
存储 算法 数据可视化
深入解析力扣159题:至多包含两个不同字符的最长子串(滑动窗口法详细图解)
深入解析力扣159题:至多包含两个不同字符的最长子串(滑动窗口法详细图解)
|
1天前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-2
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题
|
1天前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-1
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题