1.O(n2) 可優(yōu)化
int lengthOfLongestSubstring(string s) {
set<char> set;
int maxnum=0;
for(int i=0;i<s.size();i++){
set.clear();
set.insert(s[i]);
maxnum = max(maxnum,1);
for(int j=i+1;j<s.size();j++){
if(set.find(s[j])==set.end()){
set.insert(s[j]);
maxnum = max(maxnum,j-i+1);
}else{
break;
}
}
}
return maxnum;
}
2.O(n) （其實(shí)是2n浸赫，可優(yōu)化）
int lengthOfLongestSubstring(string s) {
set<char> set;
int maxnum=0;
int i=0,j=0;
while(i<s.size() && j<s.size()){
if(set.find(s[j]) == set.end()){
set.insert(s[j]);
maxnum = max(maxnum,j-i+1);
j++;
}else{
j=++i;
set.clear();
}
}
return maxnum;
}
3.優(yōu)化
思路：就像是一個框一樣，如果碰到相同的辫诅，直接跳到不同的那里
比如涧狮，“abcdac” 從第一個位置開始炕矮，遇到了第二個a，則i右移跳過重復(fù)的a档痪，即i=1+1邢滑；接著移動腐螟，遇到了第二個c困后，則i跳過重復(fù)的c，即i=3+1
int lengthOfLongestSubstring(string s) {
unordered_map<char,int> map;
int res;
for(int i=0,j=0;j<s.size();j++){
if(map.find(s[j])!=map.end()) i = max(map[s[j]],i);
res = max(res,j-i+1);
map[s[j]] = j+1;
}
return res;
}
