无重复字符的最长子串

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

示例 1:

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

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

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

时间复杂度O(NK),K是最长不重复子串的长度。其实还可以优化的，在顺序查找重复字符的索引时，可以修改为查表，可优化成O（N）。只不过数组要保存的就是对应的字母的索引值。另外最大长度也可以直接用max直接判断即可，而不需要vector。下图给出了对应做法。

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if(s.length() == 0) return 0;
        int str[1000] = {0};
        int len = 0;
        vector<int>res;//保存长度            *int mx = 0*
        int left = 0, right = 0;
        for(; right<s.length(); ) {
            //遇到重复字母的处理
            if(str[s[right]] == 1) { 
                res.push_back(len);//先存放当前长度      *mx = max(mx, len)*
                str[s[right]] = 0;//目的为了寻找左窗口
                while(str[s[left]]) {//按顺序查找第一个和已重复的字母的首位置
                    str[s[left]] = 0;//重复字母前面的字符舍去
                    ++left;
                }
                ++left;//窗口左移，去掉重复字
                len = right-left;//剩余窗口内的数字个数。
            }
            ++len;
            str[s[right]] = 1;
            ++right;
        }
        res.push_back(len);//记录最后一次长度      *return max(mx, len)*
        sort(res.begin(), res.end());
        return res[res.size()-1];
    }
};

优化完全版，线性时间。

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if(s.length() == 0) return 0;
        int str[128] = {0};
        int len = 0, mx = 0;
        int left = 0, right = 0;//窗口
        while (right<s.length()){
            //遇到重复字母的处理
            if(str[s[right]]>left) { 
                mx = max(len, mx);
                left = str[s[right]];//移动左窗口
                len = right-left;//剩余窗口内的数字个数。
            }
            ++len;
            str[s[right]] = right + 1;//保存索引值+1；
            ++right;
        }
        return max(mx, len);
    }
};