leecode第三題（無重複字元的最長子串）

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int len=s.size();
        if(len==0||len==1)//邊界
            return len;
        
        vector<int> is_here;
        for(int i=0;i<256;i++)//ASCII字元一共256個，建立一個輔助空間存儲每個字元最後出現的位置
            is_here.push_back(-1);
        
        int max_length=0;
        int j=0;//維護兩個變量，一個i是目前檢測到的字元，一個j是i字元之前無重複的最長子串
        for(int i=0;i<len;i++)
        {
            int index=s[i];
            
            if(is_here[index]<j)//如果這個字元還沒見過，或者在j之前，肯定不會重複
                is_here[index]=i;
            else//但是如果在j之後，j就得移到這個字元之後，然後記錄這個字元最後出現的位置，也就是i
            {
                j=is_here[index]+1;
                is_here[index]=i;
            }
            
            if(i-j>max_length)//i-j就是目前最長子串長度，記錄全局的
                max_length=i-j;
        }
        
        return max_length+1;
    }
};      

分析：

Hi，I’m back~這個題一開始審錯了，我以為字元串裡就隻有字母字元呢，其實任意字元都行，于是輔助空間從26改到256，還以為空間炸了，其實還好，名次還是很靠前的。

時間複雜度O（n），這個還是比較好的，也是拿空間換來的，思想就在注釋裡~

轉載于:https://www.cnblogs.com/CJT-blog/p/10799997.html