3. Longest Substring Without Repeating Characters
題目：
Given a string, find the length of the longest substring without repeating characters.
Example:
Given "abcabcbb", the answer is "abc", which the length is 3.
Given "bbbbb", the answer is "b", with the length of 1.
Given "pwwkew", the answer is "wke", with the length of 3.
Note that the answer must be a substring, "pwke" is a subsequence and not a substring.
解法一
解析
用一個(gè)map記錄各個(gè)字符的下標(biāo)著角，首先將所有的下表初始化為-1，然后向后遍歷的過程中記錄當(dāng)前字符的下標(biāo)髓削，并將當(dāng)前字符的下標(biāo)與上一個(gè)相同字符的下標(biāo)做差值彬坏，即可得到它們之間無重復(fù)字符的子串连躏。然后用Max記錄更新最大子串?dāng)?shù)，并更新map存儲的下標(biāo)值，即從這個(gè)重復(fù)值重新開始數(shù)字符串的數(shù)（最大無重復(fù)字符子串必定在兩個(gè)重復(fù)字符之間听隐，或者是整個(gè)字符串的長度）
這種方法好像被叫做滑動窗口法
"滑動窗口"
比方說 abcabccc 當(dāng)你右邊掃描到abca的時(shí)候你得把第一個(gè)a刪掉得到bca军拟，
然后"窗口"繼續(xù)向右滑動剃执，每當(dāng)加到一個(gè)新char的時(shí)候，左邊檢查有無重復(fù)的char懈息，
然后如果沒有重復(fù)的就正常添加肾档，
有重復(fù)的話就左邊扔掉一部分（從最左到重復(fù)char這段扔掉），在這個(gè)過程中記錄最大窗口長度
代碼（C++）
class Solution {
public:
int lengthOfLongestSubstring(string s) {
map<char,int> book;
int i,Max=0,pre=-1;
for(i=0;i<s.length();i++)
book[s[i]]=-1;
for(i=0;i<s.length();i++)
{
pre=max(pre,book[s[i]]);//更新map中各個(gè)字符的下標(biāo)
Max=max(Max,i-pre); //保存暫時(shí)的最大無重復(fù)子串長度
book[s[i]]=i; //計(jì)算差值后繼續(xù)更新
}
return Max;
}
};
解法二
解析
建立一個(gè)256位大小的整型數(shù)組來代替哈希表辫继，這樣做的原因是ASCII表共能表示256個(gè)字符怒见，所以可以記錄所有字符，然后我們需要定義兩個(gè)變量res和left姑宽，其中res用來記錄最長無重復(fù)子串的長度遣耍，left指向該無重復(fù)子串左邊的起始位置，然后我們遍歷整個(gè)字符串低千，對于每一個(gè)遍歷到的字符配阵，如果哈希表中該字符串對應(yīng)的值為0，說明沒有遇到過該字符示血，則此時(shí)計(jì)算最長無重復(fù)子串棋傍，i - left +１，其中ｉ是最長無重復(fù)子串最右邊的位置难审，left是最左邊的位置瘫拣，還有一種情況也需要計(jì)算最長無重復(fù)子串，就是當(dāng)哈希表中的值小于left告喊，這是由于此時(shí)出現(xiàn)過重復(fù)的字符麸拄，left的位置更新了派昧，如果又遇到了新的字符，就要重新計(jì)算最長無重復(fù)子串拢切。最后每次都要在哈希表中將當(dāng)前字符對應(yīng)的值賦值為i+1蒂萎。
代碼（C++）
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int m[256] = {0}, res = 0, left = 0;
for (int i = 0; i < s.size(); ++i) {
if (m[s[i]] == 0 || m[s[i]] < left) {
res = max(res, i - left + 1);
} else {
left = m[s[i]];
}
m[s[i]] = i + 1;
}
return res;
}
};
