很傷心，很傷心

我的。。

我的。。

別人的。。

別人的。。

想說點(diǎn)什么的。。

題目

要求從一個(gè)字符串中尋找一個(gè)子字符串，要求是，連續(xù)，沒有重復(fù)字符。返回子字符串的長(zhǎng)度即可。

題目

分析

我是這樣想的，從頭開始查找，如果有重復(fù)的字符，那么返回重復(fù)字符的下一個(gè)字符的位置重復(fù)查找，每次返回的時(shí)候記錄此時(shí)構(gòu)建的字符串長(zhǎng)度。
這樣的的話，需要一個(gè)容器存放構(gòu)建的字符串，string明顯不符合要求。因?yàn)檫€需要記住下標(biāo)，嗯，用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();
    //判斷是否重復(fù)了
    nextInTmp = (tmp.find(s[i]) != tmp.end());
    if(nextInTmp){
        //如果重復(fù)了
        //讓i=重復(fù)的那個(gè)字符的下標(biāo)
        //for循環(huán)的時(shí)候會(huì)讓他+1
        //就變成了，該字符的下一個(gè)字符
        i = tmp[s[i]];
        //清空這個(gè)map
        tmp.clear();
    }else{
        //如果沒有重復(fù)，那么添加進(jìn)去
        tmp.insert(make_pair(s[i],i));
        tmpLen = tmp.size();
        //對(duì)比一下最大的長(zhǎng)度
        if(tmpLen > maxLen){
            maxLen = tmpLen;
        }
    }
}
return maxLen; 
}

嗯，這是中規(guī)中矩的。。也是最笨的了吧。

缺點(diǎn)

重復(fù)構(gòu)造字符串，沒有很好的處理子字符串開始位置改變這種情況。

不要用改變for中的i，開重復(fù)執(zhí)行。

別人的

看了排名靠前的代碼，居然。。。字符都當(dāng)做整數(shù)來處理+不構(gòu)造字符串，同樣使用下標(biāo)來記錄是否存在。

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;
}

可能看不懂，我解釋一下。

1. 用來構(gòu)造字符串的容器。只是記錄有還是沒有，初始化為-1，意思是不存在這個(gè)字符。

vector<int>v(256,-1);

2. start用來記錄子字符串開始的位置，初始化為-1，表示沒有開始構(gòu)造子字符串。

start=-1;

3. 這里的意思是，之前這個(gè)某個(gè)字符已經(jīng)存在過了，也就是說，已經(jīng)在該字符出現(xiàn)之前出現(xiàn)過相同的字符了，（在4里面介紹）那么就將start也就是開始位置標(biāo)記為上次該字符的出現(xiàn)位置。

if(v[s[i]]>start)
    start=v[s[i]];

4. 這里，如果字符出現(xiàn)了，那么在容器中對(duì)應(yīng)的下標(biāo)，賦值為該字符在字符串中出現(xiàn)的下標(biāo)。配合3.來使用。

v[s[i]]=i;

5. i-start的意思是，當(dāng)前for循環(huán)的i（也就是子字符串的結(jié)束字符）減去子字符串結(jié)束的字符的下標(biāo)位置，結(jié)果就是子字符串的長(zhǎng)度。

ans=max(ans,i-start);

就這樣。
它使用講字符轉(zhuǎn)化為int作為vector的下標(biāo)，同時(shí)將值作為在string中的下標(biāo)，以此來省略自己構(gòu)造字符串。
并且，如果重復(fù)的字符不是子字符串的第一個(gè)字符，也可以很好改變子字符串的開始位置。
而我的“算法”，差在重復(fù)的、返回的構(gòu)造子字符串。

＃啟示

總結(jié)不出來。。