LeetCode 第3题 无重复字符的最长子串(小白详解)
无重复字符的最长字串
一、题目描述
无重复字符的最长子串 难度：中等
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: “abcabcbb” 输出: 3 解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。
示例 2:
输入: “bbbbb” 输出: 1 解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。
示例 3:
输入: “pwwkew” 输出: 3 解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，“pwke” 是一个子序列，不是子串。
通过次数561,007 提交次数1,601,892
二、个人思路及解答
这个题，乍一看，感觉应该使用滑动窗口+桶来解决。 初步思路是，求得以窗口右侧right结尾的最长的无重复字符串。当依次将 right 从1滑动至字符串尾部时，（除以s[0]外）以字符串中任意下标结尾的最长的无重复字符串将全部遍历完毕，最大值自然就出来了。 那么问题来了：在已知【以right-1为结尾的最长无重复串的】左端点的基础上，的如何求【以right为下标结尾的最长的无重复字符串】呢？答案是：在【以right-1为结尾的最长无重复串】中，必然没有重复字符，而加入了s[right]之后，可能会与【以right-1为结尾的最长无重复串】中的某个字符重复。如果无重复，则本次长度为：right-left+1；如果有一个重复，此时就需要调整left为：right-(重复字符的下标+1)+1。
使用的数据结构：桶
首先，既然是字符串，每个字符必然是0-255中的任意字符，所以可以建立256个桶。（在时间复杂度上次优的办法是hashMap，再次就是暴力） 接下来，使用两个左右指针，依次为窗口的左右侧。 最后，是用来记录maxLength的局部变量。
C++代码
int lengthOfLongestSubstring(string s) {
if (s.length() == 0) {
return 0;
}
int bucket[256];
for (int i = 0; i < 256; i++) {
bucket[i] = -1;
}
// left指向当前非重复字符串的起始字符，right指向当前非重复字符串的下一个即将判断的字符
int left = 0, right = 0;
int maxLength = 0;
while(right != s.length()) {
if(bucket[s[right]] < left) {
// 该下标在left左侧，则不影响新添加的右侧字符，且尝试更新长度
if(right-left+1 > maxLength)
maxLength = right-left+1;
} else { // 否则位于left及其右侧，需要调整左指针位置
left = bucket[s[right]]+1;
}
bucket[s[right]] = right; // 更新桶中元素
right++; // 指向下一个待判断的字符
}
return maxLength;
}三、官方题解
官方给出三种解法：多重循环、HashMap优化、桶优化。与个人思路基本一致，不再赘述，详情请参照官方题解。