https://leetcode-cn.com/problems/longest-substring-without-repeating-characters
给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是子串的长度，"pwke" 是一个子序列，不是子串。
首先，想到最直观的方法：暴力滑动窗口
用两个指针分别表示滑动窗口的开始位置和结束位置，
开始位置遍历整个字符串，
?结束位置从开始位置依次向后滑动，
??滑动过程中，用哈希表检查窗口中是否存在重复字符，
??如存在，就停止滑动，看是否更新最长滑动窗口的大小
优化一下这个过程
比如：字符串abcabcbb，
第一步，开始位置为字符串的第一个字符，不断滑动结束位置
当到达 (abc）abcbb 后，下一步就存在重复字符，停止滑动
开始位置指向下一个字符， a（bc）abcbb，
此时，不必对结束位置调到开始位置，因为滑动窗口内的字符是不会存在重复字符的
因此，结束位置继续从原来的位置向后滑动即可
注意，调整开始位置时，记得从哈希表中删除原来开始位置的字符
复杂度分析：
时间复杂度：\(O(n)\)
开始位置遍历了整个字符串
而结束位置最多也就遍历所有的ASCII码字符集，总共128个
空间复杂度：\(O(∣\Sigma∣)\)
其中, Σ 表示字符集,|Σ|表示字符集的个数
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int result = 0;
unordered_set<char> set;
int n = s.size();
for(int left = 0, right = -1; left < n; left++){
while(right + 1 < n && set.count(s[right + 1]) == 0){
set.insert(s[right + 1]);
right++;
}
result = max(result, right - left + 1);
set.erase(s[left]);
}
return result;
}
};
class Solution {
public int lengthOfLongestSubstring(String s) {
int result = 0;
Set<Character> set = new HashSet<Character>();
int n = s.length();
for(int left = 0, right = -1; left < n; left++){
while(right + 1 < n && !set.contains(s.charAt(right + 1))){
set.add(s.charAt(right + 1));
right++;
}
result = Math.max(result, right - left + 1);
set.remove(s.charAt(left));
}
return result;
}
}
原文：https://www.cnblogs.com/crazyBlogs/p/13053652.html