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

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

问题

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

示例：

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

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

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

解答

这是一道经典的双指针的题。看到这道题，最开始的想法是用动态规划，可以在平方时间内完成。然后，看到这道题有个双指针的tag，便发现可以用双指针来写。

一个指针在前面探路，如果发现遇到了重复的字符（用一个hash table来判断是否重复，但是因为字符的缘故，所以用了一个数组来判断，节省空间），那么就让另外一个指针移到与重复字符的字符的前面。然后，继续前行。

用"abcabcbb"作为例子，前面的指针j到了第二个a，就重复了，那么i就移到第一个a前面，然后继续。但是，j又遇到了b，那么重复前面的操作。直到j到了n就结束。

这样做的时间复杂度是O(n)，空间复杂度也是O(n)。

class Solution {
public:    
    int lengthOfLongestSubstring(string s) {
        int result = 0, n = s.size(), i = 0, j = 0;
        vector<int> index_map(128, -1);
        while (i < n && j < n) {
            index_map[s[i]] = i;
            j++;
            while (index_map[s[j]] == -1 && j < n) {
                index_map[s[j]] = j;
                ++j;
            }
            result = max(j - i, result);
            while (i <= index_map[s[j]]) {
                index_map[s[i]] = -1;
                ++i;
            }
            index_map[s[j]] = j; 
        }
        return result;
    }
};