题目链接：
题目描述：
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
算法：
首先，我们不需要记录子串，只需要记录对应的下标即可。对于空字符串，我们直接返回长度为0，否则我们默认最长子串的长度为1。设
m = 0，n = 1，maxSize = 1。可知，子串的范围为[m, n - 1]。然后，我们每次都比较第n个字符子串范围内有没有出现，假设没有出现，则n = n + 1。如果在第k个位置出现，则m = k + 1。最后，我们输出这个过程中最大的m - n。由于我们要遍历一遍字符串，同时n每增加一次，我们都要遍历一次子串，算法时间复杂度为，空间复杂度为
。
我们可以通过map优化查找n是否出现在子串中的过程。这样，只需要找一次map就可以知道对应的第n个字符是否在[m, n - 1]中出现，而不需要遍历。算法时间复杂度为
，由于使用了map，所以空间复杂度为
代码：
class Solution {
public:
int lengthOfLongestSubstring(string s) {
if (s.length() == 0)
return 0;
int m = 0, n = 1;
int maxSize = 1;
while(n < s.length()) {
for (int i = m; i < n; i++) {
if (s[i] == s[n])
m = i + 1;
}
n++;
maxSize = n - m > maxSize ? n - m : maxSize;
}
return maxSize;
}
};
class Solution {
public:
int lengthOfLongestSubstring(string s) {
if (s.length() == 0)
return 0;
int m = 0, n = 1;
int maxSize = 1;
map<int, int> label;
label[s[0]] = 1;
while(n < s.length()) {
if (label[s[n]] != 0 && label[s[n]] > m)
m = label[s[n]];
label[s[n]] = n + 1;
n++;
maxSize = n - m > maxSize ? n - m : maxSize;
}
return maxSize;
}
};
