leetcode学习笔记：Longest Substring Without Repeating Characters，leetcoderepeating

leetcode学习笔记：Longest Substring Without Repeating Characters，leetcoderepeating

Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.

一拿到这道题，首先就用暴力的方法，代码如下

  

    int lengthOfLongestSubstring1(string s) {
        if(s.length()<=0) return 0;
        int currentLength=1,maxLength=1;
        for(int i=1;i<s.length();++i){
            int next=findChar(s,i-currentLength,i-1,s[i]);
            if(next==-1){
                ++currentLength;
            }else{
                if(currentLength>maxLength){
                    maxLength=currentLength;
                }
                currentLength=next-(i-currentLength);
                i=next+1;
                
            }
        }
        return maxLength;
        
    }
    int findChar(const string &s,int start,int end,char c){
        for(int i=start;i<=end;++i){
            if(s[i]==c){
                return i;
            }
        }
        return -1;
    }

但是当字符串很长的时候，时间复杂度过高，囧rz , AC不了，超时了……

再想一下，好吧，用map吧，思想也很简单，代码如下：

       int lengthOfLongestSubstring(string s) {
        if(s.length()<=0) return 0;
        int next=0,maxLength=0;
        map<char,bool> mapChar;
        map<char,bool>::iterator iter;
        for(int i=0;i<s.length();++i){
            iter=mapChar.find(s[i]);
            if(iter==mapChar.end()){
                mapChar.insert(pair<char,bool>(s[i],true));
            }else{
                if(iter->second){
                    maxLength=max(maxLength,i-next);
                    while(s[next]!=s[i]){
                        mapChar[s[next]]=false;
                        ++next;
                    }
                    ++next;
                }else{
                     mapChar[s[i]]=true;
                }
            }
        }
        maxLength=max(maxLength,int(s.length()-next));
        
        return maxLength;
        
    }