算法描述

最长不重复子串其实有两种解法：
一种是yxcls那种，利用哈西表(unordered_map)来做，这种方法的基本思路就是只要当前新加入关键字的value值为1，那么说明当前的字符之前从未出现过，更合理的解释是在双指针区间i和j之间没有出现过，于是此时的结果就是j-i+1；如果加入当前值之后，其value值大于1，意味着其在区间i和j之前出现了至少了两次，于是我们需要右移i值，直到hash[s[j]]==1;为什么这么做合理呢？为什么说只要hash[s[j]]==1我们就得到了以s[j]为结尾的不重复子串的最长子串呢？加入i和j-1是一段不重复子串，如果加入s[j]之后，hash[s[j]]>1；也就意味除了s[j]所代表字符之外其余的字符出现的次数都是1次，我们需要从当前的i出发，右移，直到干掉之前出现的s[i]==s[j]即可。此处必须要注意的是在i右移的过程中，需要将s[i]对应的hash值–，此举的措施是将之前的值刨除，让hash表中存储的value一直是i和j之间的元素的个数。当然鉴于之前说过，除了s[j]所代表的字符出现了大于两次，其余字符均为一次，此处也可以将被刨除的字符对应的hash值设置为0，也可以。
复杂度o(n)

算法1

class Solution {
public:
    int longestSubstringWithoutDuplication(string s) {
        int n = s.size();
        if(n <= 1) return n;
        int res = 0;
        unordered_map<char,int> hash;
        for(int i = 0, j = 0; j < n; j ++ )
        {
            if(++hash[s[j]] > 1)
            {
                while(i < j)
                {
                    hash[s[i]]--;
                    i++;
                    if(hash[s[j]] == 1) break;
                }
            }
            res = max(res, j - i + 1);
        }
        return res;
    }
};

算法2

(动态规划) $O(n)$

因为我们可以很明显的看出，当前字符加入的时候，他的状态可以由两种状态来设定，第一是从f[i-1]转移，但是由于s[i]可能出现了不止一次，所以其实需要将f[i-1]和s[j]最近两次出现的区间长度做比较，选择最短的那个作为f[i]的状态。

C++ 代码

class Solution {
public:
    int longestSubstringWithoutDuplication(string s) {
        int n = s.size();
        if(n <=1 ) return n;
        vector<int> f(n,0);
        f[0] = 1;
        int arr[256]{0};
        for( int i = 1; i < 256; i ++ ) arr[i] = -1;
        arr[s[0]] = 0;
        int res = 0;
        for( int i = 1; i < n; i ++ )
        {
            if(arr[s[i]] == -1) {
                arr[s[i]] = i;
                f[i] = f[i - 1] + 1;
                if(res < f[i]) res = f[i];
                //cout << f[i] << endl;
            }else{
                f[i] = min(f[i - 1] + 1, i - arr[s[i]]);
                arr[s[i]] = i;
                if(res < f[i]) res = f[i];
                //cout << f[i] << endl;
            }
        }
        return res;
    }
};