很伤心，很伤心

我的。。

我的。。

别人的。。

别人的。。

想说点什么的。。

题目

要求从一个字符串中寻找一个子字符串，要求是，连续，没有重复字符。返回子字符串的长度即可。

题目

分析

我是这样想的，从头开始查找，如果有重复的字符，那么返回重复字符的下一个字符的位置重复查找，每次返回的时候记录此时构建的字符串长度。
这样的的话，需要一个容器存放构建的字符串，string明显不符合要求。因为还需要记住下标，嗯，用map。

int lengthOfLongestSubstring(string s) {

map<char, int> tmp;
//是否连续
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循环的时候会让他+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; 
}

嗯，这是中规中矩的。。也是最笨的了吧。

缺点

重复构造字符串，没有很好的处理子字符串开始位置改变这种情况。

不要用改变for中的i，开重复执行。

别人的

看了排名靠前的代码，居然。。。字符都当做整数来处理+不构造字符串，同样使用下标来记录是否存在。

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. 用来构造字符串的容器。只是记录有还是没有，初始化为-1，意思是不存在这个字符。

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

2. start用来记录子字符串开始的位置，初始化为-1，表示没有开始构造子字符串。

start=-1;

3. 这里的意思是，之前这个某个字符已经存在过了，也就是说，已经在该字符出现之前出现过相同的字符了，（在4里面介绍）那么就将start也就是开始位置标记为上次该字符的出现位置。

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

4. 这里，如果字符出现了，那么在容器中对应的下标，赋值为该字符在字符串中出现的下标。配合3.来使用。

v[s[i]]=i;

5. i-start的意思是，当前for循环的i（也就是子字符串的结束字符）减去子字符串结束的字符的下标位置，结果就是子字符串的长度。

ans=max(ans,i-start);

就这样。
它使用讲字符转化为int作为vector的下标，同时将值作为在string中的下标，以此来省略自己构造字符串。
并且，如果重复的字符不是子字符串的第一个字符，也可以很好改变子字符串的开始位置。
而我的“算法”，差在重复的、返回的构造子字符串。

＃启示

总结不出来。。