一、题目
请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。
二、示例
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"，那么具体的执行流程请见下图所示：
四、代码实现
class Solution {
public int lengthOfLongestSubstring(String s) {
int result = 0, head = 0;
char[] sc = s.toCharArray();
int[] mark = new int[128];
Arrays.fill(mark, -1);
for (int i = 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;
}
return result;
}
}
今天的文章内容就这些了：
写作不易，笔者几个小时甚至数天完成的一篇文章，只愿换来您几秒钟的 点赞 & 分享 。
更多技术干货，欢迎大家关注公众号“爪哇缪斯” ~ \(o)/ ~ 「干货分享，每天更新」
网友评论