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.話不多說优烧，開始分析啦
如果沒有思路的話朽褪，暴力法肯定是可以解決的步鉴。那么這里我就不說這種解法了基括。講道理呻顽，有點嫌了哈哈采够。
如果你看了我上一篇文章:
那么你肯定可以很容易想到一種解法避诽，沒錯了廊遍，就是滑動窗口。很明顯這題的一個很好的解法就是用滑動窗口曼氛。
沒看過也沒關系，這里放一張分析圖令野，紫色區(qū)域就是我們說的"滑動窗口"搪锣。
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)滑動窗口的魅力父晶，真的是很厲害的一種解題方式了哮缺。
