给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1：
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
示例 4:
输入: s = ""
输出: 0
数据范围：
0 <= s.length <= 5 * 10^4-
s由英文字母、数字、符号和空格组成
暴力解法
这道问题的暴力解法是：
- 枚举所有的子串，
；
- 再对每一个子串，再对每一个子串判断是否有重复字符
；
因此总的时间复杂度为 。
暴力解法的优化
注意到这样的事实：
- 如果一个子串包含重复字符，那么与它有相同左端点的、长度更长的字符串一定也包含重复字符；
- 又由于题目只要求我们找最长不重复子串的 长度（只要求返回长度，不要求得到具体的子串的结果），如果已经找到了一个长度为
的子串，那么小于等于长度
基于这两点，我们就可以使用 右指针左指针交替向右移动的方式 考虑完所有暴力解法需要考虑的子串，也就是说「滑动窗口」的解法实现了「剪枝」的效果。
这里请大家在脑海里想象一下，实在在脑海里想不太明白的话，在草稿纸上做一些简单的计算就非常清楚了。
暴力解法我们需要考虑所有可能的子串，我们把它们列出表格如下。我么用数对 表示子串
s[i..j] 。
而使用滑动窗口算法我们需要考虑的子串如下图所示。
可以看出，滑动窗口算法只要右指针移动到数组的末尾程序就结束了。暴力解法需要考虑的子串的数量级是 （具体我们就不计算它了），而滑动窗口我们需要考虑的子串为
（我没有写得很具体，相信大家能明白我的意思）。
还需要解决的一个问题，如何判断子串里是否有重复的字符，很容易想到使用「哈希表」统计字符出现次数。注意到题目的「数据范围」里说到：s 由英文字母、数字、符号和空格组成。我们还可以使用数组代替哈希表，事实上哈希表的底层也是数组。
- 当右指针向右移动将字符纳入滑动窗口的时候，字符的频数加 1；
- 当左指针向右移动将字符移出滑动窗口的时候，字符的频数减 1。
其它细节我们就不赘述了。请见「参考代码」：
public class Solution {
public int lengthOfLongestSubstring(String s) {
int len = s.length();
if (len < 2) {
return len;
}
// 当 window 中某个字符的频数为 2 时，表示滑动窗口内有重复字符
// 频数数组，128 由测试数据的范围决定
int[] freq = new int[128];
// 转换为字符数组，避免每一次 s.charAt() 方法检查下标越界
char[] charArray = s.toCharArray();
int left = 0;
int right = 0;
int res = 1;
// 循环不变量：区间[left..right] 内没有重复元素
while (right < len) {
freq[charArray[right]]++;
// 此时 [left..right) 内如果没有重复元素，就尝试扩张 right
// 否则缩小左边界，while 循环体内不断缩小边界
if (freq[charArray[right]] == 2) {
while (freq[charArray[right]] == 2) {
freq[charArray[left]]--;
left++;
}
}
// 此时 [left..right] 内没有重复元素
res = Math.max(res, right - left + 1);
right++;
}
return res;
}
}
时间复杂度：右指针遍历了数组一次、左指针还没有遍历到数组的末尾就停了下来，因此时间复杂度为 。
本题小结：
滑动窗口的问题基本上都可以写成「双重循环」的样子，其中：
- 外层循环让右指针向右移动；
- 内层循环让左指针向右移动。
在「力扣」的题解区有很多大佬提供了代码的模板，但是我们在这里建议大家通过练习去理解每一行代码的意思，不同的问题具体细节不一样，不可以生搬硬套。
欢迎大家关注我的公众号「算法不好玩」，B 站搜索「liweiwei1419」，我讲解的算法知识特别好懂。
