LeetCode OJ -- 无重复字符的最长子串

给定一个字符串，找出不含有重复字符的 最长子串 的长度。

示例：

给定 "abcabcbb" ，没有重复字符的最长子串是 "abc" ，那么长度就是3。

给定 "bbbbb" ，最长的子串就是 "b" ，长度是1。

给定 "pwwkew" ，最长子串是 "wke" ，长度是3。请注意答案必须是一个子串，"pwke" 是 子序列 而不是子串。

 

 class Solution {
 public:
     int lengthOfLongestSubstring(string s) {

         /* 实现方式采用了一遍过的方式，将所有字符和最近出现位置存储于map中，
         map查找效率O( log(n) )。遍历一次O(n) ,效率为O( nlog(n) )         */
         int i = 0;
         map<char, int> mp;
         int Max = 0;  //表示最大子串大小
         int nBegin = 0;  //最大子串的开始位置
         int nEnd = 0;    //最大子串的结束位置
         int bRepet = false; //判断字符串是否开始出现重复字符
         int nLastRptA1 = 0;    //当前重复字符倒数第二次出现的位置
         int nLastRptA2 = 0;    //当前重复字符出现的位置
         for (; i<s.size(); i++)
         {
             char tmp = s[i];
             map<char, int>::iterator mapIte = mp.find(tmp);  //
             if (mapIte == mp.end())  //第一种情况
             {
                 mp.insert(pair<char, int>(tmp, i));
                 if (!bRepet)
                 {
                     Max++;
                     nEnd = i;
                 }
                 else
                 {        //第二种情况
                     int LastRtpDur = nLastRptA2 - nLastRptA1;
                     int nNewMax = LastRtpDur + i - nLastRptA2;
                     Max = (nNewMax > Max) ? nNewMax : Max;
                     nBegin = nLastRptA1 + 1;
                     nEnd = i;
                 }
             }
             else
             {
                 bRepet = true;
                 if (mapIte->second >= nLastRptA1)        //第三种情况
                 {
                     int tmp = i - mapIte->second;
                     Max = (tmp > Max) ? tmp : Max;
                     if (tmp > Max)
                     {
                         nBegin = mapIte->second + 1;
                         nEnd = i;
                     }
                     nLastRptA1 = mapIte->second;
                     nLastRptA2 = i;
                     mapIte->second = i;
                 }
                 else {        //第四种情况
                     int tmp = i - nLastRptA1;
                     Max = (tmp > Max) ? tmp : Max;
                     if (tmp > Max)
                     {
                         nBegin = nLastRptA1 + 1;
                         nEnd = i;
                     }
                     //nLastRptA1 = mapIte->second;
                     // nLastRptA2 = i;
                     mapIte->second = i;
                 }

             }
         }
         return Max;
     }
 };

983个测试用例用时：20ms

下面是用时最短（16ms）的代码：

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int length=s.size();
        int pre = -1;
        int m[128];
        memset(m,-1,128*sizeof(int));
        int maxlength = 0;
        //int count=0;
        for(int i=0;i<length;i++)
        {
            pre = max(pre,m[s[i]]);
            maxlength = max(maxlength,i-pre);
            m[s[i]]=i;
        }
        
        return maxlength;
    }
};