给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
题目解析
题目的关键在于，如何定义不重复、最长子串两个概念。
满足这个定义的字符串必须满足两个条件：
- 字符串是连续的, 也就是说，在这个串的左边和右边各增加一部分，就能得到原字符串，不能在中间增加任何字符。
- 字符串中所有字符都只能出现1次
解法：滑动窗口法
滑动窗口法是解决字符串处理问题的一个常用方法，特别适合处理这种“遍历子序列然后求值”的问题。
滑动窗口法的基本思想是，用i,j来表示当前关注的这个子串的起点和终点，那么子串就是这一段了（除了最初
），我们每次检查
s[j+1]处的字符，如果它是不重复的，就让j向前滑动一个单位（也就是j++）；如果它重复了，那么就让i向前滑动一个单位，j不变，直到不重复为止。
可是，如果仔细想想，i如果每次只滑动一位，效率太低了！比如窗口内是aaaaaabbbbbbbbc下一个字符是c，那要等到i滑动多少次，j才能继续滑动啊，太慢了！
所以，就让i直接滑动到它该去的地方吧，假设字符s[j+1]与子串中的s[k]冲突，那么i就应该滑动到k+1这个位置！
OK，思路已经全部理清，现在来写代码吧！
int lengthOfLongestSubstring(string s) {
int n, i = 0, j, k, maxLen = 0;
n = s.size();
for (j = 0; j < n; j++) {
for (k = i; k < j; k++){//检查是否有重复字符
if (s[k] == s[j]) {
i = k + 1;//有重复，i跳到k+1，结束检查
break;
}
}
if (j - i + 1 > maxLen)//看一下当前的子串是不是最长的
maxLen = j - i + 1;
}
return maxLen;
}
复杂度分析
这个解法的空间复杂度是
时间复杂度，最坏的情况下是, 但是在原题的测试用例下表现非常好，超过了99.5%的答案，比用stl还快！
用STL的解法
然而在一般情况下，stl的效率还是很高的，如果增加很多特例，stl的表现还是会更稳定一些，所以这里还是贴出STL代码供参考。
#include<iostream>
#include<string>
#include<algorithm>
#include<map>
using namespace std;
class Solution {
public:
/*
滑动窗口法，i为窗口的起点，j为窗口的终点
map的key-value对为（字符，字符被存入map时的j+1）后面这个值代表了遇到重复字符时，i应该跳到的位置
j一直保持自增，i不自增，i的增长只靠窗口的滑动
*/
int lengthOfLongestSubstring(string s) {
int n = s.length(), maxLen = 0;
map<char, int> map;
for (int i = 0, j = 0; j < n; j++){
if (map.find(s[j]) != map.end()) {
//这里不用把跳过的字符全都删掉，如果s[j]是之前跳过的，map[s[j]]一定小于i，只要保持i不变就行，这样s[j]在后续的步骤就会像新字符那样处理
i = max(map.find(s[j])->second, i);
}
maxLen = max(maxLen, j - i + 1);
map[s[j]] = j + 1;
}
return maxLen;
}
};
时间复杂度
空间复杂度
网友评论