Given a string, find the length of the longest substring without repeating characters.
Examples:
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.
大致意思：給一個字符串俱恶，找到最長子串的長度涧郊，要求該子串不包含重復的字符。
常規(guī)解法：用哈希表來進行查找，這樣查找效率會高些捶箱。從字符串頭部開始計算子串，將沒有重復出現(xiàn)的字符存入哈希表中页响，如果遇到相同的字符闺魏，表明當前不重復子串已經結束，記錄此不重復子串的長度，并從哈希表中查到的該重復字符位置開始重新計算子串蜕径，比較確定此子串是否是當前最長的两踏，遍歷整個字符串后得到不重復字符的最長子串長度。
class Solution {
public:
int lengthOfLongestSubstring(string s) {
unordered_map<char, int> m;
int maxLen = 0;
int start = -1;
for(int i=0; i<s.size(); i++) {
auto it = m.find(s[i]);
if((it != m.end()) && (it->second >= start)) {
start = it->second;
}
m[s[i]] = i;
maxLen = max(maxLen, i-start);
}
return maxLen;
}
};
其他解法：上面用哈希表進行查詢雖然相比常規(guī)查詢要節(jié)省時間兜喻，但是我們還可以通過更簡潔的方法來實現(xiàn)梦染。我們可以用一種更巧妙的方法，因為一個字符占一個字節(jié)朴皆，八位帕识，字符的ascii范圍是在256范圍內的，我們可以建立一個256大小的數組遂铡，每次字符的查詢可以直接通過數組元素地址直接尋址肮疗，每一個數組元素的下標就是該字符的ascii值，該數組元素的值是該字符出現(xiàn)在字符串中的位置忧便，每次遍歷字符串中的字符族吻，如果沒出現(xiàn)重復則元素為默認值，累計字符串長度珠增，如果出現(xiàn)重復則將元素值置為當前字符位置超歌，并且重新計算長度，這樣依次遍歷完蒂教，計算出最長子串長度巍举，時間復雜度會更低。
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int maxlen=0;
int start=-1;
vector<int> vt(256,-1);
for(int i=0;i<s.size();++i)
{
if(vt[s[i]]>start)
{
start=vt[s[i]];
}
vt[s[i]]=i;
maxlen=max(maxlen,i-start);
}
return maxlen;
}
};
