一、题目
请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。
二、示例
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变量中。还有不要忘记了更新字符x在mark中的最新下标位置。
- 这样经过上面的流程遍历完字符串
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^)/ ~ 「干货分享，每天更新」
