Leetcode题库第3题 无重复长度的最长子串

题目概要：

题目叙述还是很清楚的，要求我们找出字符串中的一个子串，这个子串的没有重复字符，而且比这个子串长度还长的子串必定有重复出现的字符。

一开始我想到的是“滑动窗口”，窗口长度从2开始逐步增加到字符串本身的长度，窗口一次移动一格，如果当前窗口没有检测到重复字符，说明这个长度是可行的，窗口长度加1，如果检测到重复字符，窗口移一格再检测，一直做下去，直到窗口长度到最大（答案就是len(str)）或当前窗口已经滑到末尾了还是有重复字符，则答案就是窗口长度减1。我一开始想的反掉了。

这个思路是正确的，其实就是暴力法，一个个子串都去试，原始方法的代码是这样的：

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

int n = s.size();
if(n <= 1) return n; //字符串长度为1直接返回
//从窗口长度为2开始试，直到窗口长度为整个字符串的长度n
for(int len = 2; len <= n; len++){
bool found = false;

//滑动窗口，窗口的起始位置为0，1，2…，起始位置最多到n-1-(len-1)
for(int start = 0; start <= n-len; start++){
bool hasDup = false; //确定该窗口有无重复字符
for(int i = start; i < start + len; i++){
for(int j = i + 1; j < start + len; j++){
if(s[i] == s[j]){
hasDup = true;
break;
}
}
}
//只要当前窗口无重复字符，说明这个长度len可行
if(hasDup == false){
found = true;
break;
}
}

//当前长度不可行，答案就是上一个长度
if(found == false){
return len – 1;
}
}
return n; //如果len都遍历完了，那答案就是整个字符串的长度

}
};

原始方法虽然简单，写起来和理解起来还是挺费劲的，这有四层循环，前两层是确定窗口长度以及移动窗口，里面两层是用来比较这个窗口是否有字符重复。

不出我所料，也不出Kimi所料，代码在运行到倒数第二个测试用例超时了

优化思路依旧是空间换时间，这个窗口不必要逐一滑动并重置，而是可以“跳变”的。Kimi又发挥出了它惊人的天赋。图解如下：

R的位置是一直递增的，L与R之间窗口中的字符用一个字典记录它最后一次在窗口中出现的位置，由于R是从0开始移动的，我们实时更新字典其实就是记录R指针所在的字符是否需要更新，检测的也是R位置所在的字符是否出现重复。

L指针在检测到重复字符时要么不动，要么移动到 字典记录的 R指针所在字符 的 下一个位置，如何移动就取较大者。这样做的原因是当前窗口最右侧字符如果是重复出现的话，窗口的左边界绝不可能更靠左。

下面是代码，用的是数组式的伪哈希表，ASCII字符有128种，数组第一维长度为128，这样做可以快一点。

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

vector<int> last(128,-1); //记录每一种字符最后一次出现的位置，-1表示未出现过
int left = 0;
int maxLen = 0;
for(int right = 0; right < s.size(); right++){
char ch = s[right];
//如果字符出现过，且大于left，left跳变，合起来就是：
if(last[ch] >= left){ //这里是大于等于
left= last[ch] + 1;
}
last[ch] = right; //实时更新last
maxLen = max(maxLen, right – left + 1); //实时更新maxLen
}
return maxLen;
}
};

当然，题目仅限ASCII字符，如果有汉字等其他字符，可以将128改成Unicode的65536，或者用真正的哈希表，代码做了些改动，注意初始化和访问方式。

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

unordered_map <char, int> last;
int left = 0;
int maxLen = 0;
for(int right = 0; right < s.size(); right++){
char ch = s[right];
int last_ch = last.count(ch) ? last[ch] : -1;
//如果字符出现过，且大于left，left跳变，合起来就是：
if(last_ch >= left){ //这里是大于等于
left= last[ch] + 1;
}
last[ch] = right; //实时更新last
maxLen = max(maxLen, right – left + 1); //实时更新maxLen
}
return maxLen;

}
};