LeetCode 3：Longest Substring Without Repeating Characters（最長不含重復字符的子串）

Q:Given a string, find the length of the longest substring without repeating characters.

我是翻譯君:
給定一個字符串，找到不含重復字符的最長子串

1.可能需要和面試官溝通的問題

這里的字符是只含有字母還是字母加數(shù)字，還是ASCII的所有字符集

2.話不多說，開始分析啦

如果沒有思路的話，暴力法肯定是可以解決的。那么這里我就不說這種解法了。講道理，有點嫌了哈哈。

如果你看了我上一篇文章:

LeetCode 209：長度最小的子數(shù)組

那么你肯定可以很容易想到一種解法，沒錯了，就是滑動窗口。很明顯這題的一個很好的解法就是用滑動窗口。

沒看過也沒關系，這里放一張分析圖，紫色區(qū)域就是我們說的"滑動窗口"。

repeatstring.jpg

4.就憑這個一小窗口就可以解決問題？是可以的，那么端好小板凳，拿好小本本，下面劃重點了

（1）定義滑動窗口的區(qū)間[l,r],初始為[0,-1],也即是區(qū)間無元素

（2）初始化最大子串長度為0

（3）定義一個數(shù)組存儲字符元素的重復出現(xiàn)的次數(shù)

（4）開始滑動窗口，窗口為出界并且當r指針指向的字符未出現(xiàn)時候，r指針右移。當r指針指向的字符不是第一次出現(xiàn)時候，l指針右移。

（5）最后利用max函數(shù)找到最長的子串

int lengthOfLongestSubstring(string s) {
        int l=0;
        int r=-1;             //1.定義滑動窗口的區(qū)間[l,r],初始為[0,-1],也即是區(qū)間無元素
        int len=0;            //2.最大子串長度
        int freq[256]={0};   //3.定義一個數(shù)組存儲字符元素的重復出現(xiàn)的次數(shù)

        //開始滑動窗口
        while(l<s.size()){
            if(r+1<s.size()&&freq[s[r+1]]==0){ //窗口為出界并且當r指針指向的字符未出現(xiàn)時候，r指針右移
                r++;
                freq[s[r]]++;  
            }
            else{
                freq[s[l]]--;                   //r指針指向的字符不是第一次出現(xiàn)時候，l指針右移
                l++;
            }

            len=max(len,r-l+1);                 //找到最長的子串
        }
        return len;

    }

這里面有個小技巧，怎么樣只利用O（1）的時間復雜度求出一段字符串里某個字符沒有重復呢？

沒錯，就是上面的一個長度為256的數(shù)組

int freq[256]={0};

因為字符肯定都是在ASCII編碼里，共256個，那么掃描到某個字符時，就會對應到該字符的ASCII碼，也就會對應成數(shù)組的下標了。初始話所有字符出現(xiàn)次數(shù)都為0，如果掃描到一次，對應的次數(shù)就加1.

freq[s[r+1]]==0

通過這個字符在數(shù)組的值是否為0來判斷是否出現(xiàn)過，從而讓窗口進行移動（縮小或擴大）

到這里是不是發(fā)現(xiàn)滑動窗口的魅力，真的是很厲害的一種解題方式了。