問題
Given a string, find the length of the longest substring without repeating characters.
Example 1:
Input: "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
Example 2:
Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
Example 3:
Input: "pwwkew"
Output: 3
Explanation: 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.
最長不重復(fù)字串問題：給定一個字符串纺铭，找出字符串中的最長不重復(fù)字串醋火，返回其字符串長度。
分析
首先想到的是O(N^2)方法闯参，針對可能的每個字符子串進行查找，計算長度。
保持一個字符串左邊界，右邊界不斷移動剑梳，判斷當(dāng)前字符串[left, right]是否是不重復(fù)字串。如果是滑潘，計算長度垢乙；如果不是，更換左邊界语卤。
左邊界更換的觸發(fā)條件是當(dāng)前字符s[right]追逮，在字符串s[left, right-1]中出現(xiàn)了酪刀；否則，即沒有出現(xiàn)在子串當(dāng)中钮孵，計算當(dāng)前字符串長度骂倘。
- 如果出現(xiàn)在子串中，更換左邊界：左邊界換為當(dāng)前字符在數(shù)據(jù)中存儲位置的下一位巴席；
- 如果沒出現(xiàn)在字串中历涝，此時有兩種情況：確實沒出現(xiàn)；出現(xiàn)位置不在子串窗口范圍內(nèi)荧库，即位置<left
為了方便，這里使用一個字典存儲字符與下一次重復(fù)時左邊界的移動位置分衫。
還有一個問題是子串長度什么時候計算的問題般此。是字符發(fā)生重復(fù)時丐箩，還是沒有重復(fù)字符？
如果是有字符重復(fù)時計算恤煞，那么有一種情況為整個子串都沒有重復(fù)字符，此時施籍，一直不會觸發(fā)長度計算；所以喜喂，理想情況是沒有發(fā)生字符重復(fù)時||重復(fù)字符不在窗口范圍內(nèi)，此時計算子串長度竿裂。
代碼
class Solution {
public:
int lengthOfLongestSubstring(string s) {
if (s.empty()) return 0;
int result = 0, left = 0, right = 0;
//unordered_map<char, int> dict;
vector<int> dict(256, 0);//字符做下標(biāo)
while (right < s.size()){
if (dict[s[right]] == 0 || dict[s[right]] < left)
result = max(right - left + 1, result);
else
left = dict[s[right]];
dict[s[right]] = right + 1;
right++;
}
return result;
}
};
