2018-01-27

最长无重复子串

与 最长重复子串 不一样的是，此问题要求所有子串中没有重复字母的子串中长度最长为多少。

题目来源为 Leetcode 第三题 Longest Substring Without Repeating Characters

基本思路是用的滑动窗口来遍历每个起始点的无重复子串的长度，然后取得最大的长度。

首先来个简单易懂的每次清空hash表

int lengthOfLongestSubstring(string s) {
        string str = s;
        int max = 0;
        for(int i = 0; i < str.length(); ++i)
        {
            unordered_map<char,int> map;
            map[str[i]] = 1;
            int j = 0;
            for(j = i+1; j < str.length() && map[str[j]] != 1; ++j)
            {
                map[str[j]] = 1;
            }
            if(j - i > max)
            {
                 max = j - i;
            }
        }
        return max;
    }

同样的思路，来个升级版时间复杂度 O(2n) abababababab这种为最坏情况

int lengthOfLongestSubstring(string s) {
    string str = s;
    int max = 0;
    const int len = str.length();
    int i = 0, j = 0;
    unordered_map<char,int> map;
    while(i < len && j < len)
    {
        if(map[str[j]] == 1)//左边前移 区间变短
        {
            map[str[i++]]--;
        }
        else//右边前移 区间变长 更新 max
        {
            map[str[j++]]++;
            if(j - i > max)
                max = j - i;
        }

    }
    return max;
}