Longest Substring Without Repeating Characters 是一道非常经典的字符串题。
题目要求我们在一个字符串中，找到不含重复字符的最长子串，并返回这个子串的长度。
这道题通常有两种思路：
-
暴力枚举
-
滑动窗口 + HashMap 优化
下面按照这两种方式来分析。
题目示例
输入：s = "abcabcbb"
输出：3
解释：因为无重复字符的最长子串是 "abc"，所以长度为 3
再看一个例子：
输入：s = "bbbbb"
输出：1
解释：因为无重复字符的最长子串是 "b"，所以长度为 1
一、暴力枚举
最直接的思路是：
-
枚举每一个位置作为结尾
-
然后向前寻找，直到出现重复字符为止
-
在这个过程中更新答案
这就是一种典型的暴力做法。
暴力代码（带注释）
class Solution {
public int lengthOfLongestSubstring(String s) {
// ans 用来记录当前找到的最长无重复子串长度
int ans = 0;
// 枚举每一个位置 i，把它看作子串的结尾位置
for (int i = 0; i < s.length(); i++) {
// 用布尔数组记录当前枚举过程中字符是否出现过
// 这里默认字符集较小，可以直接用数组做标记
boolean[] tar = new boolean[300];
// 从位置 i 开始，向左枚举
for (int j = i; j >= 0; j--) {
// 如果当前字符已经出现过，说明出现重复，直接结束本轮
if (tar[s.charAt(j)]) {
break;
}
// 标记当前字符已经出现
tar[s.charAt(j)] = true;
// 更新最长长度
ans = Math.max(ans, i - j + 1);
}
}
return ans;
}
}
暴力思路分析
假设字符串是：
"abcabcbb"
当我们枚举到某个位置 i 时：
-
从
i开始向前找 -
只要没有重复字符，就继续扩大这个子串
-
一旦发现重复字符，就停止
比如以字符 c 结尾时，我们往前可以得到 "abc"； 再继续往前时如果出现重复，就不能再扩展了。
暴力解法复杂度分析
时间复杂度
O(n^2)
原因是：
-
外层循环枚举每个位置
-
内层循环最坏情况下会一直往前扫描
所以整体是平方级别复杂度。
空间复杂度
O(1)
这里使用的是固定大小的布尔数组，空间不随输入规模增长，因此可以看作常数空间。
说明：如果严格从字符集通用性出发，这种写法依赖字符范围。 在 LeetCode 这道题的常见数据范围下，这样写是可以工作的。
二、滑动窗口 + HashMap 优化
暴力解法的问题在于：
很多字符被重复扫描了。
能不能做到：
-
遇到重复字符时，不再回头重新检查
-
而是直接把左边界移动到合适位置
这就是滑动窗口的核心思想。
我们可以使用一个 HashMap<Character, Integer> 来记录字符最近一次出现的位置，从而快速更新窗口左边界。
优化代码（带注释）
import java.util.HashMap;
class Solution {
public int lengthOfLongestSubstring(String s) {
// map 记录字符最近一次出现的位置
// 这里保存的是“下标 + 1”，这样写可以方便处理左边界更新
HashMap<Character, Integer> map = new HashMap<>();
// ans 记录当前最长无重复子串长度
int ans = 0;
// i 表示窗口右边界，j 表示窗口左边界
for (int i = 0, j = 0; i < s.length(); i++) {
// 如果当前字符之前出现过
if (map.containsKey(s.charAt(i))) {
// 更新左边界
// 取最大值是为了防止左边界回退
j = Math.max(j, map.get(s.charAt(i)));
}
// 以当前 i 作为右边界，更新答案
ans = Math.max(ans, i - j + 1);
// 记录当前字符最新出现的位置
// 注意这里存的是 i + 1
map.put(s.charAt(i), i + 1);
}
return ans;
}
}
为什么 map.put(s.charAt(i), i + 1) 要存 i + 1？
这是这道题里一个非常容易让人迷惑的点。
我们先看这句：
j = Math.max(j, map.get(s.charAt(i)));
这里的 j 表示的是当前窗口的左边界。
如果某个字符之前出现过，那么左边界应该直接跳到：
这个字符上一次出现位置的下一个位置
所以在 map 里直接存 i + 1，就可以在更新左边界时少写一步运算，代码更简洁。
优化思路演示
以字符串：
"abcabcbb"
为例。
初始状态
-
i = 0 -
j = 0 -
窗口为空
当扫描到 'a'
-
'a'没出现过 -
当前窗口是
"a" -
长度为
1
记录：
map['a'] = 1
当扫描到 'b'
-
'b'没出现过 -
当前窗口是
"ab" -
长度为
2
记录：
map['b'] = 2
当扫描到 'c'
-
'c'没出现过 -
当前窗口是
"abc" -
长度为
3
记录：
map['c'] = 3
当再次扫描到 'a'
-
'a'之前出现过 -
它上一次出现后一个位置是
1 -
所以左边界更新为
j = 1
此时窗口变成：
"bca"
仍然保持无重复。
这就是滑动窗口“向前滑动”的本质。
为什么更新左边界时要写 Math.max(j, map.get(...))？
因为左边界只能向右移动，不能回退。
举个例子：
如果当前窗口左边界已经在比较靠右的位置，而某个字符虽然之前出现过，但它出现的位置在当前窗口左边界之前，那么这个重复其实对当前窗口没有影响。
所以必须写成：
j = Math.max(j, map.get(s.charAt(i)));
这样才能保证窗口始终合法。
优化解法复杂度分析
时间复杂度
O(n)
因为每个字符最多被访问有限次，左右指针整体只会向前移动。
空间复杂度
O(k)
其中 k 是字符集里实际出现在窗口中的不同字符数量。
如果按最坏情况来写，也可以记作：
O(min(n, 字符集大小))
在日常题解中，通常也会简化写成 O(n)。
这道题的核心思想
这题最重要的并不是背代码，而是理解这两个点：
1. 窗口中不能出现重复字符
所以一旦有重复，就要移动左边界。
2. 左边界不回退
即使某个字符之前出现过，也要判断它的上次出现位置是否真的落在当前窗口内。
这就是为什么要使用 Math.max(...)。
两种解法对比
暴力枚举
优点：
-
思路直观
-
容易想到
-
适合刚开始理解题意时使用
缺点：
-
存在大量重复扫描
-
时间复杂度较高
滑动窗口 + HashMap
优点：
-
只需要线性扫描
-
性能更好
-
是这道题的标准解法
缺点：
-
初学时不太容易想到
-
对窗口边界的更新要求更细致
总结
无重复字符的最长子串 是滑动窗口的代表题之一。
它非常适合用来理解：
-
什么是滑动窗口
-
什么是窗口左边界和右边界
-
-
为什么左边界不能回退
如果你把这道题真正理解透了，后面很多字符串窗口题都会轻松很多。
适合直接发布的结尾
刷这道题时，建议按下面的顺序来练：
-
先自己写出暴力解法
-
明确暴力做法哪里有重复计算
-
再理解滑动窗口为什么能避免重复扫描
-
最后彻底吃透
HashMap + 双指针的写法
很多字符串题，本质上都是在维护一个“合法窗口”。
