给定一个字符串，找出不含有重复字符的 最长子串 的长度。
示例：
给定 "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 = ;
map<char, int> mp;
int Max = ; //表示最大子串大小
int nBegin = ; //最大子串的开始位置
int nEnd = ; //最大子串的结束位置
int bRepet = false; //判断字符串是否开始出现重复字符
int nLastRptA1 = ; //当前重复字符倒数第二次出现的位置
int nLastRptA2 = ; //当前重复字符出现的位置
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 + ;
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 + ;
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 + ;
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 = -;
int m[];
memset(m,-,*sizeof(int));
int maxlength = ;
//int count=0;
for(int i=;i<length;i++)
{
pre = max(pre,m[s[i]]);
maxlength = max(maxlength,i-pre);
m[s[i]]=i;
}
return maxlength;
}
};