【每日leecode】Leecode 3. 无重复字符的最长子串

3. 无重复字符的最长子串

难度中等3591

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法：

1. 首先建立一个长度为128的map对string中以及有的byte进行记录，加 1 表示从字符位置后一个才开始不重复
2. 另外维护开始和结束下标（滑动窗口），对于本题每次end下标正常自增，当kvmap中出现了end的值说明以及重复，对start下标进行重新赋值，当end下标到达string的最后循环退出。
3. 每次在滑动窗口的时候记录当前窗口的长度，并与最大的长度进行对比，如果更大则进行更新
4. 循环最后需要把经历过的值塞入map， 加 1 表示从字符位置后一个才开始不重复，并且很多情况下为0的时候不好判断
5. 返回最大值
6. 本次解题利用了数组替代了数组，如果string是只包含字母 还可以进行 -'a'的操作把string落入长度26的数组中

go代码

func lengthOfLongestSubstring(s string) int {
    val := []byte(s) //将string转为byte的切片
    kvmap := make([]int, 128)//对于acs码 128 大小足够，kvmap的下标对应val切片的值，kvmap的value对应的是在val中该值最大的index
    ans, num := 0, 0 //ans 用于记录最大的结果， num 用于记录当前窗口的大小
    for start,end := 0,0 ;end < len(val); end++ { //双指针进行循环 start 的位置需要判断后前进，end每次前进，end到达最后就可以结束了
        if kvmap[val[end]] > start { //如果map中已经有start的值需要重置start
            start = kvmap[val[end]]
        }
        num = end - start + 1
        if num > ans {
            ans = num //每次得出窗口和最大值比较
        }
        kvmap[val[end]] = end + 1 //把经历过的值塞入map， +1 是为了方便处理
    }
    return ans
}

c++代码

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        vector<int> kvmap(128, 0);//注意数组的初始化
        int lens = s.size();
        int ans = 0;
        int start = 0;
        for (int end = 0; end < lens; end++) {
            start = max(start, kvmap[s[end]]);
            ans = max(ans, end - start + 1);
            kvmap[s[end]] = end + 1;
        } 
        return ans;
    }
};