本文最后编辑于 前，其中的内容可能需要更新。
题目描述：
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
1
2
3
| 输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
|
示例 2:
1
2
3
| 输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
|
示例 3:
1
2
3
4
| 输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
|
示例 4:
提示：
- $0 <= s.length <= 5 * 10^4$
- $s$ 由英文字母、数字、符号和空格组成
链接：
https://leetcode-cn.com/problems/longest-substring-without-repeating-characters
题目分析
由于题目要求寻找的子串是连续的，则我们可以使用滑动窗口的思想。也就是说，right 向右遍历添加字符进入窗口，而当添加的字符与窗口中已有字符重复时，我们将左边的字符移出窗口，直到字符不再重复。而我们维护这样一个窗口，若窗口是目前最大长度时，对这个长度进行记录即可。查找字符是否存在使用一个哈希表解决。注意字符串为空的情况直接返回 0。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public:
int lengthOfLongestSubstring(string s) {
if(s.size() == 0) return 0;
int left = 0, res = 0;
unordered_set<char> alpha;
for(int right = 0; right < s.size(); right++){
while(alpha.find(s[right]) != alpha.end()){
alpha.erase(s[left]);
left++;
}
alpha.insert(s[right]);
res = max(res, right-left+1);
}
return res;
}
};
|
时间复杂度：$O(n)$，$n$ 是字符串的长度。滑动窗口的两头指针分别遍历了一次字符串。
空间复杂度：$O(|\Sigma|)$，$\Sigma$ 是字符串中出现过的字符集，$|\Sigma|$ 表示字符集的大小。因为我们需要维护字符串出现过的字符构成的哈希表。