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

好久没刷，突然发现，leetcode 出中文版了。。

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

示例：

给定 "abcabcbb" ，没有重复字符的最长子串是 "abc" ，那么长度就是3。

给定 "bbbbb" ，最长的子串就是 "b" ，长度是1。

给定 "pwwkew" ，最长子串是 "wke" ，长度是3。请注意答案必须是一个子串，"pwke" 是 子序列 而不是子串。

---

看到这题，

1. 因为要看的是无重复字符的子串，先考虑怎么判断字符串字符串里头有没有这个字符，可以用一个128个元素的大数组进行标记，字符串里有的字符，对应位置就标为1，不在标为0 。
2. 除了标为0和1，还可以在数组里头标记子二个字符在字符串s出现的位置，就是下标。用两个变量，start和end分别标记这个子串的开始和结束的位置。标记数组里的值不在start到end的范围就说明子串里头没有这个字符。
3. 初始化的子串是，只有第一个字符，因此start和end初值都是0，子串的长度是end - start + 1,遍历这个字符串，这个字符要是子串里头没有，就把这个字符加到子串里，就是end+1。这字符要是串里头存在的话，就是，要把子串前端一直到第一次出现这个字符的部分全不移除，再把这个字符加进去。那个数组记录的字符的下标就有用了，（例如： "dabacd", 在遍历完第一个b的时候，子串是"dab"，下一个遍历第二个a,结果应该是"ba",要把第一个a，以及之前的字符全去掉，也就是要把start移动到第一个a的后边一个，也就是，table[idx] + 1 ）这时候就把start = table[idx] + 1,就把子串的start移动过去了。最后每次遍历判断一下字符串长度就好了。

---

代码如下：

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if(s.size() == 0)
            return 0;
        else if(s.size() == 1)
            return 1;
        vector<int> table(256, -1); //初始值是-1 
        int c = s[0];
        table[c] = 0;
        int start = 0; // 头
        int end = 0; // 尾   //初始化的子串只有第一个字符
        int res = 1; 
        for(int i = 1; i < s.size(); i++)
        {
            int idx = s[i];
            if(table[idx] < start) // 不在串里头
            {
                //把这个数加进去 
                table[idx] = i;  
                end = i;
            }
            else //出现过是重复的
            {
                start = table[idx] + 1; 
                table[idx] = i;
                end = i;
            }
            int len = end - start + 1; //加入新字符 后 的串的长度
            if(len >= res)
            {
                res = len;
            }
        }
        return res;
    }
};