很傷心泪喊，很傷心
我的。勤晚。
我的。领虹。
別人的。菌羽。
別人的掠械。。
想說點什么的注祖。猾蒂。
題目
要求從一個字符串中尋找一個子字符串，要求是是晨，連續(xù)肚菠，沒有重復字符。返回子字符串的長度即可罩缴。
題目
分析
我是這樣想的蚊逢，從頭開始查找，如果有重復的字符箫章，那么返回重復字符的下一個字符的位置重復查找烙荷，每次返回的時候記錄此時構(gòu)建的字符串長度。
這樣的的話檬寂，需要一個容器存放構(gòu)建的字符串终抽，string明顯不符合要求。因為還需要記住下標桶至，嗯昼伴，用map。
int lengthOfLongestSubstring(string s) {
map<char, int> tmp;
//是否連續(xù)
bool nextInTmp = false;
int len = s.length();
int maxLen = 0;
for(int i = 0;i < len; i++){
int tmpLen = tmp.size();
//判斷是否重復了
nextInTmp = (tmp.find(s[i]) != tmp.end());
if(nextInTmp){
//如果重復了
//讓i=重復的那個字符的下標
//for循環(huán)的時候會讓他+1
//就變成了镣屹，該字符的下一個字符
i = tmp[s[i]];
//清空這個map
tmp.clear();
}else{
//如果沒有重復圃郊，那么添加進去
tmp.insert(make_pair(s[i],i));
tmpLen = tmp.size();
//對比一下最大的長度
if(tmpLen > maxLen){
maxLen = tmpLen;
}
}
}
return maxLen;
}
嗯，這是中規(guī)中矩的女蜈。持舆。也是最笨的了吧。
缺點
重復構(gòu)造字符串伪窖，沒有很好的處理子字符串開始位置改變這種情況吏廉。
不要用改變for中的i，開重復執(zhí)行惰许。
別人的
看了排名靠前的代碼，居然史辙。汹买。佩伤。字符都當做整數(shù)來處理+不構(gòu)造字符串，同樣使用下標來記錄是否存在晦毙。
int lengthOfLongestSubstring(string s) {
vector<int>v(256,-1);
int len=s.size(),ans=0,start=-1;
for(int i=0;i<len;i++){
if(v[s[i]]>start)//Slding window
start=v[s[i]];
v[s[i]]=i;
ans=max(ans,i-start);
}
return ans;
}
可能看不懂生巡，我解釋一下。
- 用來構(gòu)造字符串的容器见妒。只是記錄有還是沒有孤荣，初始化為-1，意思是不存在這個字符须揣。
vector<int>v(256,-1);
-
start用來記錄子字符串開始的位置盐股，初始化為-1，表示沒有開始構(gòu)造子字符串耻卡。
start=-1;
- 這里的意思是疯汁，之前這個某個字符已經(jīng)存在過了，也就是說卵酪，已經(jīng)在該字符出現(xiàn)之前出現(xiàn)過相同的字符了幌蚊，（在4里面介紹）那么就將
start也就是開始位置標記為上次該字符的出現(xiàn)位置。
if(v[s[i]]>start)
start=v[s[i]];
- 這里溃卡，如果字符出現(xiàn)了溢豆，那么在容器中對應的下標，賦值為該字符在字符串中出現(xiàn)的下標瘸羡。配合3.來使用漩仙。
v[s[i]]=i;
-
i-start的意思是，當前for循環(huán)的i（也就是子字符串的結(jié)束字符）減去子字符串結(jié)束的字符的下標位置最铁，結(jié)果就是子字符串的長度讯赏。
ans=max(ans,i-start);
就這樣。
它使用講字符轉(zhuǎn)化為int作為vector的下標冷尉，同時將值作為在string中的下標漱挎，以此來省略自己構(gòu)造字符串。
并且雀哨，如果重復的字符不是子字符串的第一個字符磕谅，也可以很好改變子字符串的開始位置。
而我的“算法”雾棺，差在重復的膊夹、返回的構(gòu)造子字符串。
＃啟示
總結(jié)不出來捌浩。放刨。
