作者：whisper

链接：https://www.proprogrammar.com/article/890

声明：请尊重原作者的劳动，如需转载请注明出处

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

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

示例 1:

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

示例 2:

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

示例 3:

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

提示：

• s.length <= 40000

难度：中等；标签：哈希表，双指针，滑动窗口；编程语言：C++

我的解法

class Solution {
public:
    // 想法：用辅助数组
    int lengthOfLongestSubstring(string s) {
        int aid[256], longest = 0, start = 0, len = s.length();
        fill(aid, aid+256, -1);

        for(int i = 0; i < len; i++){
            if(aid[s[i] - ' '] == -1){
                aid[s[i] - ' '] = i;
            }else{
                longest = max(longest, i - start);
                for(int j = start; j <= aid[s[i] - ' '] - 1; j++){
                    aid[s[j] - ' '] = -1;
                }
                start = max(start, aid[s[i] - ' '] + 1);
                aid[s[i] - ' '] = i;
            }
        }

        return max(longest, len - start);
    }
};

用一个数组记录字符第一次出现的位置，用start记录当前无重复字符的子串的开始位置，如果字符再次（第二次）出现，更新结果，同时更新start为字符第一次出现位置之后一个位置，这样该字符在当前子串中只出现一次

其它解法

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int map[128]={0},len=0,start=0;
        for(int i=0;i<s.length();i++){
            ++map[s[i]];
            while(map[s[i]]==2){
                --map[s[start++]];
            }
            len = max(len,i-start+1);

        }
        return len;
    }
};

和我的解法方法是一样的，不过这里代码比较简短，同时也不是很好理解了，理解了我的解法再看这里就比较好理解了（方法是差不多一样的）

亲爱的读者：有时间可以点赞评论一下