【CodeTop 001】3. 无重复字符的最长子串
🎯 难度：中等（Medium）
📚 标签：哈希表、字符串、滑动窗口
🔗 题目链接：https://leetcode.cn/problems/longest-substring-without-repeating-characters/
🏷️ 所属专题：CodeTop 大厂高频面试题
[TOC]
一、题目描述
1.1 官方原题
给定一个字符串 s，请你找出其中不含有重复字符的 最长子串 的长度。
1.2 数据范围
0 <= s.length <= 5 * 10^4s由英文字母、数字、符号和空格组成
二、题目理解（新手必看）
2.1 什么是”子串”？
子串（Substring） 是指字符串中连续的一段字符。
原字符串： "abcdef"
子串的例子：
✅ "abc" （位置0-2，连续）
✅ "bcd" （位置1-3，连续）
✅ "cdef" （位置2-5，连续）
✅ "a" （位置0，单个字符也是子串）
✅ "abcdef" （整个字符串也是子串）
不是子串的例子：
❌ "ace" （a、c、e 不连续，这叫"子序列"）
❌ "adf" （不连续）关键区分：
- 子串：必须连续（substring）
- 子序列：可以不连续，但顺序不变（subsequence）
2.2 什么是”无重复字符”？
无重复字符 是指子串中每个字符都只出现一次。
✅ 无重复字符的子串：
"abc" → a、b、c 各出现1次
"xyz" → x、y、z 各出现1次
"a1b2" → a、1、b、2 各出现1次
❌ 有重复字符的子串：
"abca" → a 出现了2次
"aab" → a 出现了2次
"abcabc" → a、b、c 都出现了2次2.3 用生活例子理解
想象你在排队买票，队伍里每个人拿着一张写有字母的牌子。现在你要找到最长的一段连续队伍，使得这段队伍中每个人的牌子上的字母都不一样。
队伍： [a] [b] [c] [a] [b] [c] [b] [b]
位置： 0 1 2 3 4 5 6 7
从位置0开始看：
- 位置0: a ✓
- 位置1: b ✓ （目前队伍：ab，没有重复）
- 位置2: c ✓ （目前队伍：abc，没有重复）
- 位置3: a ✗ （a 在位置0已经出现过了！）
所以从位置0开始，最长无重复子串是 "abc"，长度为3。2.4 这道题要我们做什么？
目标：在整个字符串中，找出所有可能的无重复字符子串，返回其中最长的那个的长度。
注意：题目只要求返回长度，不需要返回子串本身。
三、输入输出说明
3.1 输入格式
| 参数 | 类型 | 说明 |
|---|---|---|
| s | String | 输入字符串，长度范围 [0, 50000]，可包含字母、数字、符号和空格 |
3.2 输出格式
| 返回值 | 类型 | 说明 |
|---|---|---|
| result | int | 最长无重复字符子串的长度 |
四、示例详解
4.1 示例1：基础情况
输入：s = "abcabcbb"
输出：3
解释：因为无重复字符的最长子串是 "abc"，所以其长度为 3。分析过程
字符串：a b c a b c b b
索引： 0 1 2 3 4 5 6 7
让我们列出所有可能的无重复字符子串：
从位置0开始：
├── "a" 长度1 ✓
├── "ab" 长度2 ✓
├── "abc" 长度3 ✓
└── "abca" ❌ (a重复了)
从位置1开始：
├── "b" 长度1 ✓
├── "bc" 长度2 ✓
├── "bca" 长度3 ✓
└── "bcab" ❌ (b重复了)
从位置2开始：
├── "c" 长度1 ✓
├── "ca" 长度2 ✓
├── "cab" 长度3 ✓
└── "cabc" ❌ (c重复了)
从位置3开始：
├── "a" 长度1 ✓
├── "ab" 长度2 ✓
├── "abc" 长度3 ✓
└── "abcb" ❌ (b重复了)
从位置4开始：
├── "b" 长度1 ✓
├── "bc" 长度2 ✓
├── "bcb" ❌ (b重复了)
从位置5开始：
├── "c" 长度1 ✓
├── "cb" 长度2 ✓
├── "cbb" ❌ (b重复了)
从位置6开始：
├── "b" 长度1 ✓
├── "bb" ❌ (b重复了)
从位置7开始：
├── "b" 长度1 ✓
最长的无重复子串长度 = 3（如 "abc"、"bca"、"cab"）4.2 示例2：全部相同字符
输入：s = "bbbbb"
输出：1
解释：因为无重复字符的最长子串是 "b"，所以其长度为 1。分析过程
字符串：b b b b b
索引： 0 1 2 3 4
无论从哪个位置开始，只要取2个或以上的字符，就会重复：
- "bb" ❌ (b重复)
- "bbb" ❌ (b重复)
- ...
所以最长无重复子串只能是单个字符 "b"，长度为1。4.3 示例3：部分重复
输入：s = "pwwkew"
输出：3
解释：因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是子串的长度，"pwke" 是一个子序列，不是子串。分析过程
字符串：p w w k e w
索引： 0 1 2 3 4 5
从位置0开始：
├── "p" 长度1 ✓
├── "pw" 长度2 ✓
└── "pww" ❌ (w重复了)
从位置1开始：
├── "w" 长度1 ✓
└── "ww" ❌ (w重复了)
从位置2开始：
├── "w" 长度1 ✓
├── "wk" 长度2 ✓
├── "wke" 长度3 ✓ ← 这是其中一个最长的！
└── "wkew" ❌ (w重复了)
从位置3开始：
├── "k" 长度1 ✓
├── "ke" 长度2 ✓
├── "kew" 长度3 ✓ ← 这也是最长的！
└── 已到末尾
从位置4开始：
├── "e" 长度1 ✓
├── "ew" 长度2 ✓
└── 已到末尾
从位置5开始：
├── "w" 长度1 ✓
└── 已到末尾
最长无重复子串长度 = 3（如 "wke" 或 "kew"）关于”pwke”的说明
题目特别指出："pwke" 是一个子序列，不是子串。
为什么？
字符串：p w w k e w
索引： 0 1 2 3 4 5
"pwke" 对应的位置是：p(0), w(1或2), k(3), e(4)
如果用 w(1)：位置是 0, 1, 3, 4 → 不连续！
如果用 w(2)：位置是 0, 2, 3, 4 → 不连续！
所以 "pwke" 不是子串（不连续），而是子序列。4.4 示例4：空字符串
输入：s = ""
输出：0
解释：空字符串没有任何字符，所以最长子串长度为0。4.5 示例5：单个字符
输入：s = "a"
输出：1
解释：整个字符串就一个字符，没有重复，长度为1。4.6 示例6：完全不重复
输入：s = "abcdefgh"
输出：8
解释：整个字符串都没有重复字符，所以答案就是整个字符串的长度。4.7 更多练习示例
| 输入 | 输出 | 解释 |
|---|---|---|
| “abba” | 2 | 最长无重复子串是 “ab” 或 “ba” |
| “dvdf” | 3 | 最长无重复子串是 “vdf” |
| “anviaj” | 5 | 最长无重复子串是 “nviaj” |
| ” “ | 1 | 空格也是一个字符，长度为1 |
| “au” | 2 | 整个字符串无重复，长度为2 |
| “aab” | 2 | 最长无重复子串是 “ab” |
五、解题思路
5.1 暴力解法（帮助理解，但效率低）
思路：枚举所有可能的子串，检查每个子串是否有重复字符，记录最长的。
步骤：
1. 用两层循环枚举所有子串的起点和终点
2. 对每个子串，检查是否有重复字符
3. 如果无重复，更新最大长度
缺点：时间复杂度 O(n³)，太慢了！5.2 滑动窗口思想（核心！）
什么是滑动窗口？
滑动窗口是一种用于处理连续子数组/子串问题的技巧。想象一个可以伸缩的窗户框架在数组/字符串上滑动。
想象你有一个透明的窗户框架，可以左右移动，也可以扩大或缩小：
字符串： a b c a b c b b
[---窗口---]
↑
窗口可以向右滑动
窗口可以扩大或缩小滑动窗口的关键点：
- 用两个指针表示窗口的左右边界：
left和right right指针向右扩大窗口- 当窗口内出现重复字符时，
left指针向右收缩窗口 - 始终保持窗口内无重复字符
5.3 为什么滑动窗口有效？
关键洞察：如果我们知道某个位置 i 到 j 的子串有重复字符，那我们就不需要再检查任何包含这个重复字符的子串了。
例如：字符串 "abcab"
当 right=3 时发现 'a' 重复：
字符串：a b c a b
↑ ↑
left right
窗口 [a,b,c,a] 有重复的 'a'
此时不需要从头检查，只需要把 left 移到重复字符的下一个位置：
字符串：a b c a b
↑ ↑
left right
窗口变成 [c,a]，没有重复了！5.4 算法步骤详解
初始化：
├── left = 0 // 窗口左边界
├── right = 0 // 窗口右边界
├── maxLen = 0 // 记录最大长度
└── Set/Map // 记录窗口内的字符
循环过程（right 从 0 遍历到末尾）：
│
├── 步骤1：尝试将 s[right] 加入窗口
│ │
│ ├── 如果 s[right] 不在窗口中：
│ │ └── 直接加入，窗口扩大
│ │
│ └── 如果 s[right] 已在窗口中（重复了）：
│ └── 不断移动 left，缩小窗口，直到没有重复
│
├── 步骤2：将 s[right] 加入窗口
│
├── 步骤3：更新最大长度
│ └── maxLen = max(maxLen, right - left + 1)
│
└── 步骤4：right++，继续下一轮
返回 maxLen5.5 图解滑动窗口过程
以 s = "abcabcbb" 为例：
═══════════════════════════════════════════════════════════════════════
第0步：初始状态
═══════════════════════════════════════════════════════════════════════
字符串： a b c a b c b b
索引： 0 1 2 3 4 5 6 7
left = 0, right = 0
窗口内容 = {}（空）
maxLen = 0
═══════════════════════════════════════════════════════════════════════
═══════════════════════════════════════════════════════════════════════
第1步：right = 0，处理字符 'a'
═══════════════════════════════════════════════════════════════════════
字符串： a b c a b c b b
[a]
↑
left/right
'a' 不在窗口中 → 加入窗口
窗口内容 = {a}
窗口长度 = 0 - 0 + 1 = 1
maxLen = max(0, 1) = 1
═══════════════════════════════════════════════════════════════════════
═══════════════════════════════════════════════════════════════════════
第2步：right = 1，处理字符 'b'
═══════════════════════════════════════════════════════════════════════
字符串： a b c a b c b b
[a b]
↑ ↑
left right
'b' 不在窗口中 → 加入窗口
窗口内容 = {a, b}
窗口长度 = 1 - 0 + 1 = 2
maxLen = max(1, 2) = 2
═══════════════════════════════════════════════════════════════════════
═══════════════════════════════════════════════════════════════════════
第3步：right = 2，处理字符 'c'
═══════════════════════════════════════════════════════════════════════
字符串： a b c a b c b b
[a b c]
↑ ↑
left right
'c' 不在窗口中 → 加入窗口
窗口内容 = {a, b, c}
窗口长度 = 2 - 0 + 1 = 3
maxLen = max(2, 3) = 3
═══════════════════════════════════════════════════════════════════════
═══════════════════════════════════════════════════════════════════════
第4步：right = 3，处理字符 'a'
═══════════════════════════════════════════════════════════════════════
字符串： a b c a b c b b
[a b c] (a) ← 'a' 重复了！
↑ ↑
left right
'a' 已在窗口中 → 需要收缩窗口！
│
├── 移除 s[0]='a'，left = 1
│ 窗口内容 = {b, c}
│ 检查：'a' 还在窗口中吗？ 不在了！
│
└── 现在可以加入新的 'a' 了
字符串： a b c a b c b b
[b c a]
↑ ↑
left right
窗口内容 = {b, c, a}
窗口长度 = 3 - 1 + 1 = 3
maxLen = max(3, 3) = 3
═══════════════════════════════════════════════════════════════════════
═══════════════════════════════════════════════════════════════════════
第5步：right = 4，处理字符 'b'
═══════════════════════════════════════════════════════════════════════
字符串： a b c a b c b b
[b c a] (b) ← 'b' 重复了！
↑ ↑
left right
'b' 已在窗口中 → 需要收缩窗口！
│
├── 移除 s[1]='b'，left = 2
│ 窗口内容 = {c, a}
│ 检查：'b' 还在窗口中吗？ 不在了！
│
└── 现在可以加入新的 'b' 了
字符串： a b c a b c b b
[c a b]
↑ ↑
left right
窗口内容 = {c, a, b}
窗口长度 = 4 - 2 + 1 = 3
maxLen = max(3, 3) = 3
═══════════════════════════════════════════════════════════════════════
═══════════════════════════════════════════════════════════════════════
第6步：right = 5，处理字符 'c'
═══════════════════════════════════════════════════════════════════════
字符串： a b c a b c b b
[c a b] (c) ← 'c' 重复了！
↑ ↑
left right
'c' 已在窗口中 → 需要收缩窗口！
│
├── 移除 s[2]='c'，left = 3
│ 窗口内容 = {a, b}
│ 检查：'c' 还在窗口中吗？ 不在了！
│
└── 现在可以加入新的 'c' 了
字符串： a b c a b c b b
[a b c]
↑ ↑
left right
窗口内容 = {a, b, c}
窗口长度 = 5 - 3 + 1 = 3
maxLen = max(3, 3) = 3
═══════════════════════════════════════════════════════════════════════
═══════════════════════════════════════════════════════════════════════
第7步：right = 6，处理字符 'b'
═══════════════════════════════════════════════════════════════════════
字符串： a b c a b c b b
[a b c] (b) ← 'b' 重复了！
↑ ↑
left right
'b' 已在窗口中 → 需要收缩窗口！
│
├── 移除 s[3]='a'，left = 4
│ 窗口内容 = {b, c}
│ 检查：'b' 还在窗口中吗？ 还在！继续收缩
│
├── 移除 s[4]='b'，left = 5
│ 窗口内容 = {c}
│ 检查：'b' 还在窗口中吗？ 不在了！
│
└── 现在可以加入新的 'b' 了
字符串： a b c a b c b b
[c b]
↑ ↑
left right
窗口内容 = {c, b}
窗口长度 = 6 - 5 + 1 = 2
maxLen = max(3, 2) = 3
═══════════════════════════════════════════════════════════════════════
═══════════════════════════════════════════════════════════════════════
第8步：right = 7，处理字符 'b'
═══════════════════════════════════════════════════════════════════════
字符串： a b c a b c b b
[c b] (b) ← 'b' 重复了！
↑ ↑
left right
'b' 已在窗口中 → 需要收缩窗口！
│
├── 移除 s[5]='c'，left = 6
│ 窗口内容 = {b}
│ 检查：'b' 还在窗口中吗？ 还在！继续收缩
│
├── 移除 s[6]='b'，left = 7
│ 窗口内容 = {}
│ 检查：'b' 还在窗口中吗？ 不在了！
│
└── 现在可以加入新的 'b' 了
字符串： a b c a b c b b
[b]
↑
left/right
窗口内容 = {b}
窗口长度 = 7 - 7 + 1 = 1
maxLen = max(3, 1) = 3
═══════════════════════════════════════════════════════════════════════
═══════════════════════════════════════════════════════════════════════
结束：right = 8，超出字符串范围，循环结束
═══════════════════════════════════════════════════════════════════════
最终答案：maxLen = 3
═══════════════════════════════════════════════════════════════════════六、代码实现
6.1 方法一：滑动窗口 + HashSet（推荐新手）
class Solution {
public int lengthOfLongestSubstring(String s) {
// 用 HashSet 存储当前窗口内的字符
Set<Character> window = new HashSet<>();
int left = 0; // 窗口左边界
int maxLen = 0; // 记录最大长度
// right 是窗口右边界，遍历整个字符串
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right); // 当前要加入窗口的字符
// 如果当前字符已在窗口中，收缩左边界
while (window.contains(c)) {
window.remove(s.charAt(left)); // 移除最左边的字符
left++; // 左边界右移
}
// 将当前字符加入窗口
window.add(c);
// 更新最大长度
maxLen = Math.max(maxLen, right - left + 1);
}
return maxLen;
}
}6.2 方法二：滑动窗口 + HashMap（优化版）
class Solution {
public int lengthOfLongestSubstring(String s) {
// HashMap 存储字符及其最新出现的位置
Map<Character, Integer> map = new HashMap<>();
int left = 0; // 窗口左边界
int maxLen = 0; // 记录最大长度
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
// 如果字符已存在，直接跳转 left 到重复字符的下一个位置
if (map.containsKey(c)) {
// 注意：取 max 是因为 left 不能往回走
left = Math.max(left, map.get(c) + 1);
}
// 更新字符的最新位置
map.put(c, right);
// 更新最大长度
maxLen = Math.max(maxLen, right - left + 1);
}
return maxLen;
}
}6.3 方法三：滑动窗口 + 数组（最高效）
class Solution {
public int lengthOfLongestSubstring(String s) {
// 用数组代替 HashMap，ASCII 码范围是 0-127
// 数组下标表示字符的 ASCII 码值
// 数组值表示该字符最新出现的位置 + 1（方便处理）
int[] charIndex = new int[128];
int left = 0; // 窗口左边界
int maxLen = 0; // 记录最大长度
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
// 如果这个字符之前出现过，更新 left
// charIndex[c] 存储的是上次出现位置 + 1
left = Math.max(left, charIndex[c]);
// 更新最大长度
maxLen = Math.max(maxLen, right - left + 1);
// 记录当前字符的位置 + 1
charIndex[c] = right + 1;
}
return maxLen;
}
}七、代码逐行解析
7.1 方法一详解（HashSet版）
class Solution {
public int lengthOfLongestSubstring(String s) {
// ==================== 第1步：创建数据结构 ====================
// HashSet 是一个集合，特点是：不允许重复元素
// 我们用它来存储当前滑动窗口内的所有字符
// 可以在 O(1) 时间内判断某个字符是否存在
Set<Character> window = new HashSet<>();
// ==================== 第2步：初始化变量 ====================
// left: 窗口的左边界（包含）
// 初始时窗口为空，从位置0开始
int left = 0;
// maxLen: 记录遍历过程中发现的最长无重复子串长度
// 初始为0，因为还没有找到任何子串
int maxLen = 0;
// ==================== 第3步：开始遍历 ====================
// right: 窗口的右边界（包含）
// right 从0遍历到字符串末尾
// 每次循环尝试将 s[right] 加入窗口
for (int right = 0; right < s.length(); right++) {
// 获取当前要处理的字符
char c = s.charAt(right);
// ==================== 第4步：处理重复 ====================
// 如果当前字符已经在窗口中，说明会产生重复
// 需要不断收缩窗口（移除左边的字符）
// 直到窗口中不再包含当前字符
while (window.contains(c)) {
// 从窗口中移除最左边的字符
window.remove(s.charAt(left));
// 左边界右移
left++;
}
// 循环结束后，窗口中一定没有字符 c
// ==================== 第5步：扩大窗口 ====================
// 将当前字符加入窗口
window.add(c);
// ==================== 第6步：更新答案 ====================
// 当前窗口的长度是：right - left + 1
// 更新最大长度
maxLen = Math.max(maxLen, right - left + 1);
}
// ==================== 第7步：返回结果 ====================
return maxLen;
}
}7.2 关键代码解释
7.2.1 为什么用 while 而不是 if？
// ❓ 为什么是 while，不是 if？
while (window.contains(c)) {
window.remove(s.charAt(left));
left++;
}原因：重复字符可能不是紧挨着 left 的那个字符。
例如：s = "abba"
当 right=3, c='a' 时：
窗口 = {b, a}（对应位置2和3）
↑
此时 'a' 在窗口中
如果用 if：
- 只移除 s[left]='b'，left=3
- 窗口 = {a}
- 但是！新的 'a'(位置3) 要加入，而旧的 'a' 还没被移除！
正确做法用 while：
- 第1次：移除 s[2]='b'，left=3，窗口={a}
- 检查：'a' 还在窗口中吗？在！
- 第2次：移除 s[3]='a'，left=4，窗口={}
- 检查：'a' 还在窗口中吗？不在了，退出循环7.2.2 窗口长度的计算
right - left + 1示例：
字符串： a b c d
索引： 0 1 2 3
如果 left=1, right=3，窗口是 [b, c, d]
长度 = 3 - 1 + 1 = 3 ✓
为什么要 +1？
因为 left 和 right 都是包含在窗口内的
区间 [1,3] 包含的元素个数 = 3 - 1 + 1 = 37.2.3 HashMap 版本中的 Math.max(left, map.get(c) + 1)
left = Math.max(left, map.get(c) + 1);为什么需要取 max？
例如：s = "abba"
状态变化：
right=0, c='a': map={a:0}, left=0
right=1, c='b': map={a:0, b:1}, left=0
right=2, c='b': map={a:0, b:2}, left=max(0, 1+1)=2
right=3, c='a': map={a:3, b:2}, left=max(2, 0+1)=???
注意 right=3 时：
- 'a' 上次出现在位置0
- 如果直接用 left = 0 + 1 = 1，那就往回走了！
- 但实际上 left 已经在位置2了，不能往回走
- 所以必须取 max(2, 1) = 2
left 只能往右走，不能往左走！八、执行过程模拟
8.1 示例 “abcabcbb” 完整执行
┌──────────────────────────────────────────────────────────────────────┐
│ 初始化 │
├──────────────────────────────────────────────────────────────────────┤
│ s = "abcabcbb" │
│ window = {}（空的HashSet） │
│ left = 0 │
│ maxLen = 0 │
└──────────────────────────────────────────────────────────────────────┘
┌──────────────────────────────────────────────────────────────────────┐
│ 循环 right = 0, c = 'a' │
├──────────────────────────────────────────────────────────────────────┤
│ window.contains('a')? No → 跳过while │
│ window.add('a') → window = {a} │
│ maxLen = max(0, 0-0+1) = max(0, 1) = 1 │
│ │
│ 状态：left=0, right=0, window={a}, maxLen=1 │
└──────────────────────────────────────────────────────────────────────┘
┌──────────────────────────────────────────────────────────────────────┐
│ 循环 right = 1, c = 'b' │
├──────────────────────────────────────────────────────────────────────┤
│ window.contains('b')? No → 跳过while │
│ window.add('b') → window = {a, b} │
│ maxLen = max(1, 1-0+1) = max(1, 2) = 2 │
│ │
│ 状态：left=0, right=1, window={a,b}, maxLen=2 │
└──────────────────────────────────────────────────────────────────────┘
┌──────────────────────────────────────────────────────────────────────┐
│ 循环 right = 2, c = 'c' │
├──────────────────────────────────────────────────────────────────────┤
│ window.contains('c')? No → 跳过while │
│ window.add('c') → window = {a, b, c} │
│ maxLen = max(2, 2-0+1) = max(2, 3) = 3 │
│ │
│ 状态：left=0, right=2, window={a,b,c}, maxLen=3 │
└──────────────────────────────────────────────────────────────────────┘
┌──────────────────────────────────────────────────────────────────────┐
│ 循环 right = 3, c = 'a' │
├──────────────────────────────────────────────────────────────────────┤
│ window.contains('a')? Yes! → 进入while │
│ ├── window.remove(s[0]='a') → window = {b, c} │
│ ├── left = 1 │
│ └── window.contains('a')? No → 退出while │
│ window.add('a') → window = {b, c, a} │
│ maxLen = max(3, 3-1+1) = max(3, 3) = 3 │
│ │
│ 状态：left=1, right=3, window={b,c,a}, maxLen=3 │
└──────────────────────────────────────────────────────────────────────┘
┌──────────────────────────────────────────────────────────────────────┐
│ 循环 right = 4, c = 'b' │
├──────────────────────────────────────────────────────────────────────┤
│ window.contains('b')? Yes! → 进入while │
│ ├── window.remove(s[1]='b') → window = {c, a} │
│ ├── left = 2 │
│ └── window.contains('b')? No → 退出while │
│ window.add('b') → window = {c, a, b} │
│ maxLen = max(3, 4-2+1) = max(3, 3) = 3 │
│ │
│ 状态：left=2, right=4, window={c,a,b}, maxLen=3 │
└──────────────────────────────────────────────────────────────────────┘
┌──────────────────────────────────────────────────────────────────────┐
│ 循环 right = 5, c = 'c' │
├──────────────────────────────────────────────────────────────────────┤
│ window.contains('c')? Yes! → 进入while │
│ ├── window.remove(s[2]='c') → window = {a, b} │
│ ├── left = 3 │
│ └── window.contains('c')? No → 退出while │
│ window.add('c') → window = {a, b, c} │
│ maxLen = max(3, 5-3+1) = max(3, 3) = 3 │
│ │
│ 状态：left=3, right=5, window={a,b,c}, maxLen=3 │
└──────────────────────────────────────────────────────────────────────┘
┌──────────────────────────────────────────────────────────────────────┐
│ 循环 right = 6, c = 'b' │
├──────────────────────────────────────────────────────────────────────┤
│ window.contains('b')? Yes! → 进入while │
│ ├── window.remove(s[3]='a') → window = {b, c} │
│ ├── left = 4 │
│ └── window.contains('b')? Yes! → 继续while │
│ ├── window.remove(s[4]='b') → window = {c} │
│ ├── left = 5 │
│ └── window.contains('b')? No → 退出while │
│ window.add('b') → window = {c, b} │
│ maxLen = max(3, 6-5+1) = max(3, 2) = 3 │
│ │
│ 状态：left=5, right=6, window={c,b}, maxLen=3 │
└──────────────────────────────────────────────────────────────────────┘
┌──────────────────────────────────────────────────────────────────────┐
│ 循环 right = 7, c = 'b' │
├──────────────────────────────────────────────────────────────────────┤
│ window.contains('b')? Yes! → 进入while │
│ ├── window.remove(s[5]='c') → window = {b} │
│ ├── left = 6 │
│ └── window.contains('b')? Yes! → 继续while │
│ ├── window.remove(s[6]='b') → window = {} │
│ ├── left = 7 │
│ └── window.contains('b')? No → 退出while │
│ window.add('b') → window = {b} │
│ maxLen = max(3, 7-7+1) = max(3, 1) = 3 │
│ │
│ 状态：left=7, right=7, window={b}, maxLen=3 │
└──────────────────────────────────────────────────────────────────────┘
┌──────────────────────────────────────────────────────────────────────┐
│ 循环结束：right = 8 >= s.length() = 8 │
├──────────────────────────────────────────────────────────────────────┤
│ 返回 maxLen = 3 │
└──────────────────────────────────────────────────────────────────────┘九、多种解法对比
9.1 解法对比表格
| 解法 | 时间复杂度 | 空间复杂度 | 优点 | 缺点 |
|---|---|---|---|---|
| 暴力枚举 | O(n³) | O(n) | 思路直观 | 效率太低 |
| HashSet | O(n) | O(min(n,m)) | 代码清晰，易理解 | 稍慢 |
| HashMap | O(n) | O(min(n,m)) | 跳跃式移动left | 需要理解max逻辑 |
| 数组 | O(n) | O(128) = O(1) | 最快，空间固定 | 只适用ASCII |
注：n 是字符串长度，m 是字符集大小
9.2 不同语言实现
Python 版本
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
# 使用字典存储字符及其最新位置
char_index = {}
left = 0
max_len = 0
for right, char in enumerate(s):
# 如果字符已存在且在当前窗口内
if char in char_index and char_index[char] >= left:
left = char_index[char] + 1
char_index[char] = right
max_len = max(max_len, right - left + 1)
return max_lenJavaScript 版本
var lengthOfLongestSubstring = function(s) {
const charSet = new Set();
let left = 0;
let maxLen = 0;
for (let right = 0; right < s.length; right++) {
// 如果字符重复，收缩窗口
while (charSet.has(s[right])) {
charSet.delete(s[left]);
left++;
}
charSet.add(s[right]);
maxLen = Math.max(maxLen, right - left + 1);
}
return maxLen;
};C++ 版本
class Solution {
public:
int lengthOfLongestSubstring(string s) {
// 使用数组记录字符位置
vector<int> charIndex(128, -1);
int left = 0;
int maxLen = 0;
for (int right = 0; right < s.size(); right++) {
char c = s[right];
// 更新 left 位置
left = max(left, charIndex[c] + 1);
charIndex[c] = right;
maxLen = max(maxLen, right - left + 1);
}
return maxLen;
}
};Go 版本
func lengthOfLongestSubstring(s string) int {
charIndex := make(map[rune]int)
left := 0
maxLen := 0
for right, char := range s {
if lastPos, exists := charIndex[char]; exists && lastPos >= left {
left = lastPos + 1
}
charIndex[char] = right
if right - left + 1 > maxLen {
maxLen = right - left + 1
}
}
return maxLen
}十、新手常见错误
10.1 错误一：忘记更新字符位置
// ❌ 错误写法
if (map.containsKey(c)) {
left = Math.max(left, map.get(c) + 1);
}
// 忘记更新 map.put(c, right) !!!
maxLen = Math.max(maxLen, right - left + 1);
// ✅ 正确写法
if (map.containsKey(c)) {
left = Math.max(left, map.get(c) + 1);
}
map.put(c, right); // 必须更新！
maxLen = Math.max(maxLen, right - left + 1);问题：如果不更新字符位置，下次遇到相同字符时会用旧的位置计算，导致错误。
10.2 错误二：left 往回走
// ❌ 错误写法
if (map.containsKey(c)) {
left = map.get(c) + 1; // 可能往回走！
}
// ✅ 正确写法
if (map.containsKey(c)) {
left = Math.max(left, map.get(c) + 1); // 保证只往前走
}问题演示：
s = "abba"
错误过程：
right=0, c='a': map={a:0}, left=0
right=1, c='b': map={a:0,b:1}, left=0
right=2, c='b': map={a:0,b:2}, left=1+1=2 ✓
right=3, c='a': map={a:3,b:2}, left=0+1=1 ✗（往回走了！）
正确过程：
right=3, c='a': left=max(2, 0+1)=2 ✓（保持在2）10.3 错误三：窗口长度计算错误
// ❌ 错误写法
maxLen = Math.max(maxLen, right - left); // 少了 +1
// ✅ 正确写法
maxLen = Math.max(maxLen, right - left + 1);问题：right - left 计算的是间隔数，不是元素个数。
left=1, right=3
元素：s[1], s[2], s[3] → 共3个
间隔：3 - 1 = 2 ← 不对！
正确：3 - 1 + 1 = 3 ✓10.4 错误四：HashSet 版本用 if 代替 while
// ❌ 错误写法
if (window.contains(c)) {
window.remove(s.charAt(left));
left++;
}
// ✅ 正确写法
while (window.contains(c)) {
window.remove(s.charAt(left));
left++;
}问题：重复字符可能不在 left 位置，需要一直移除直到没有重复。
10.5 错误五：空字符串未处理
// ❌ 可能出错的写法（如果代码逻辑有问题）
// 需要确保空字符串返回0
// ✅ 滑动窗口天然处理空字符串
// 当 s.length() == 0 时，for 循环不执行，直接返回 maxLen = 010.6 错误六：数组版本索引错误
// ❌ 错误写法：存储 right 而不是 right + 1
charIndex[c] = right;
left = Math.max(left, charIndex[c]); // 这样 left 会指向重复字符本身
// ✅ 正确写法：存储 right + 1
charIndex[c] = right + 1;
left = Math.max(left, charIndex[c]); // left 指向重复字符的下一个位置十一、边界情况处理
11.1 边界情况清单
| 情况 | 输入 | 期望输出 | 说明 |
|---|---|---|---|
| 空字符串 | “” | 0 | 没有字符 |
| 单个字符 | “a” | 1 | 整个字符串无重复 |
| 全部相同 | “aaaa” | 1 | 只能取单个字符 |
| 全部不同 | “abcd” | 4 | 整个字符串无重复 |
| 两头相同 | “abcda” | 4 | “abcd” 或 “bcda” |
| 空格 | ” “ | 1 | 空格也是字符 |
| 特殊字符 | “!@#$” | 4 | 都是不同字符 |
| 数字 | “12321” | 3 | “123” 或 “321” |
| 混合 | “a1b2c3” | 6 | 全部不重复 |
11.2 边界测试代码
public class Test {
public static void main(String[] args) {
Solution solution = new Solution();
// 基本测试
System.out.println(solution.lengthOfLongestSubstring("abcabcbb")); // 3
System.out.println(solution.lengthOfLongestSubstring("bbbbb")); // 1
System.out.println(solution.lengthOfLongestSubstring("pwwkew")); // 3
// 边界测试
System.out.println(solution.lengthOfLongestSubstring("")); // 0
System.out.println(solution.lengthOfLongestSubstring("a")); // 1
System.out.println(solution.lengthOfLongestSubstring(" ")); // 1
System.out.println(solution.lengthOfLongestSubstring("abba")); // 2
System.out.println(solution.lengthOfLongestSubstring("dvdf")); // 3
System.out.println(solution.lengthOfLongestSubstring("tmmzuxt")); // 5
}
}十二、复杂度分析
12.1 时间复杂度：O(n)
HashSet 版本分析：
外层循环：right 从 0 到 n-1，执行 n 次
内层 while 循环：left 最多从 0 移动到 n-1
关键点：left 和 right 都只会向右移动，不会回退
- right 移动 n 次
- left 最多移动 n 次
- 总操作次数 ≤ 2n
时间复杂度：O(2n) = O(n)HashMap/数组版本分析：
只有一层循环：right 从 0 到 n-1
每次循环内的操作都是 O(1)
时间复杂度：O(n)12.2 空间复杂度
HashSet/HashMap 版本：O(min(n, m))
n：字符串长度
m：字符集大小
窗口内最多存储 min(n, m) 个不同字符
- 如果字符串很短（n < m），最多存 n 个字符
- 如果字符串很长（n > m），最多存 m 个不同字符数组版本：O(1)
使用固定大小的数组（128 或 256）
不随输入规模变化
空间复杂度：O(128) = O(1)12.3 复杂度对比表
| 方法 | 时间 | 空间 | 说明 |
|---|---|---|---|
| 暴力 | O(n³) | O(n) | 三层循环 |
| HashSet | O(n) | O(min(n,m)) | 两次遍历 |
| HashMap | O(n) | O(min(n,m)) | 一次遍历 |
| 数组 | O(n) | O(1) | 一次遍历，固定空间 |
十三、滑动窗口模板总结
13.1 通用滑动窗口模板
public int slidingWindow(String s) {
// 1. 定义窗口数据结构
Map<Character, Integer> window = new HashMap<>();
// 2. 初始化左右指针
int left = 0, right = 0;
int result = 0;
// 3. 右指针遍历
while (right < s.length()) {
char c = s.charAt(right); // 将要加入窗口的字符
right++; // 右指针右移
// 4. 更新窗口数据
// ... (根据具体问题更新)
// 5. 判断是否需要收缩窗口
while (/* 收缩条件 */) {
char d = s.charAt(left); // 将要移出窗口的字符
left++; // 左指针右移
// 6. 更新窗口数据
// ... (根据具体问题更新)
}
// 7. 更新答案
// ... (根据具体问题更新)
}
return result;
}13.2 滑动窗口适用场景
- 连续子串/子数组问题
- 需要满足某种条件的最长/最短区间
- 可以用双指针表示区间边界
常见类型：
- 最长无重复子串（本题）
- 最小覆盖子串
- 找所有字母异位词
- 字符串的排列
十四、相关题目推荐
14.1 类似滑动窗口题目
| 题号 | 题目 | 难度 | 关联 |
|---|---|---|---|
| 76 | 最小覆盖子串 | 困难 | 需要收缩窗口找最小 |
| 438 | 找到字符串中所有字母异位词 | 中等 | 固定窗口大小 |
| 567 | 字符串的排列 | 中等 | 判断是否包含排列 |
| 209 | 长度最小的子数组 | 中等 | 找最短满足条件的区间 |
| 904 | 水果成篮 | 中等 | 最多两种类型的最长区间 |
| 424 | 替换后的最长重复字符 | 中等 | 允许替换k个字符 |
| 1004 | 最大连续1的个数 III | 中等 | 允许翻转k个0 |
14.2 变体问题
变体1：返回最长子串本身（而不是长度）
public String longestSubstring(String s) {
int[] charIndex = new int[128];
int left = 0;
int maxLen = 0;
int maxStart = 0; // 记录最长子串的起始位置
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
left = Math.max(left, charIndex[c]);
if (right - left + 1 > maxLen) {
maxLen = right - left + 1;
maxStart = left; // 更新起始位置
}
charIndex[c] = right + 1;
}
return s.substring(maxStart, maxStart + maxLen);
}变体2：允许k个重复字符
// 找出最多有k个重复字符的最长子串
public int lengthWithKRepeats(String s, int k) {
Map<Character, Integer> count = new HashMap<>();
int left = 0;
int maxLen = 0;
int repeats = 0; // 当前窗口中重复的字符数
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
count.put(c, count.getOrDefault(c, 0) + 1);
if (count.get(c) == 2) repeats++;
while (repeats > k) {
char d = s.charAt(left);
if (count.get(d) == 2) repeats--;
count.put(d, count.get(d) - 1);
left++;
}
maxLen = Math.max(maxLen, right - left + 1);
}
return maxLen;
}十五、常见问题 FAQ
Q1：为什么滑动窗口比暴力快？
A：暴力法需要检查所有可能的子串，有 O(n²) 个子串，每个子串检查重复需要 O(n)，总共 O(n³)。而滑动窗口利用了一个关键性质：当发现重复时，可以直接跳过不可能成为答案的子串，每个元素最多被访问两次（一次被 right 访问，一次被 left 跳过），所以是 O(n)。
Q2：HashMap 版本和 HashSet 版本有什么区别？
A：
- HashSet 版本需要用 while 循环逐个移除字符直到没有重复
- HashMap 版本记录了每个字符的位置，可以直接跳转 left 到正确位置
HashSet：遇到重复 → 循环移除直到不重复（可能移除多次）
HashMap：遇到重复 → 直接跳转到重复字符下一个位置（一步到位）Q3：为什么数组版本要存 right + 1 而不是 right？
A：存 right + 1 是为了方便处理。当我们需要让 left 跳到重复字符的下一个位置时，直接用 charIndex[c] 就是正确的新位置，不需要额外 +1。
另一种理解：charIndex[c] 表示”下次遇到字符 c 时，left 最少应该在的位置”。
Q4：如果字符串包含 Unicode 字符怎么办？
A：数组版本只适用于 ASCII 字符（0-127）。如果有 Unicode 字符，应该使用 HashMap 版本，它可以处理任意字符。
// 适用于所有字符的版本
Map<Character, Integer> map = new HashMap<>();Q5：这道题有没有可能用动态规划解决？
A：可以，但不推荐。定义 dp[i] 为以 s[i] 结尾的最长无重复子串长度：
// 动态规划思路（不推荐，理解滑动窗口更重要）
public int lengthOfLongestSubstring(String s) {
if (s.length() == 0) return 0;
Map<Character, Integer> lastPos = new HashMap<>();
int[] dp = new int[s.length()];
int maxLen = 0;
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (i == 0) {
dp[i] = 1;
} else if (!lastPos.containsKey(c)) {
dp[i] = dp[i-1] + 1;
} else {
int lastIndex = lastPos.get(c);
if (i - lastIndex > dp[i-1]) {
dp[i] = dp[i-1] + 1;
} else {
dp[i] = i - lastIndex;
}
}
lastPos.put(c, i);
maxLen = Math.max(maxLen, dp[i]);
}
return maxLen;
}本质上动态规划思路和滑动窗口是等价的，但滑动窗口更直观。
十六、知识点总结
16.1 本题涉及的核心概念
-
滑动窗口
- 用两个指针维护一个可变大小的窗口
- 窗口可以扩大（right 右移）或收缩（left 右移）
- 始终保持窗口内满足某种条件
-
哈希表
- HashSet：快速判断元素是否存在，O(1)
- HashMap：存储键值对，快速查找位置，O(1)
-
双指针
- 同向双指针：两个指针向同一方向移动
- left 和 right 都只向右移动，不回退
-
字符串操作
charAt(i)：获取第 i 个字符length()：获取字符串长度
16.2 算法技巧要点
| 技巧 | 说明 |
|---|---|
| 窗口扩张 | right 向右移动，尝试扩大窗口 |
| 窗口收缩 | 当条件不满足时，left 向右移动 |
| 条件维护 | 使用数据结构（Set/Map/数组）维护窗口状态 |
| 答案更新 | 在合适时机更新答案（通常在窗口合法时） |
十七、总结
17.1 本题要点回顾
这道题是 CodeTop 第一题，也是 LeetCode 第3题，是滑动窗口的经典入门题。
核心思想：
- 使用滑动窗口维护一个无重复字符的区间
- 右指针扩大窗口，左指针收缩窗口
- 每次窗口合法时更新最大长度
关键技巧：
- 用 HashSet 或 HashMap 快速判断字符是否重复
- left 只向右移动，不回退（保证时间复杂度）
- 使用
right - left + 1计算窗口长度
17.2 学完这道题你应该掌握
- ✅ 理解什么是滑动窗口
- ✅ 掌握滑动窗口的基本模板
- ✅ 能够使用 HashSet/HashMap 维护窗口状态
- ✅ 理解时间复杂度为什么是 O(n)
- ✅ 能够处理各种边界情况
17.3 下一步学习建议
- 练习同类题目：尝试 LeetCode 76、438、567 等滑动窗口题目
- 总结模板：整理滑动窗口的通用模板，形成肌肉记忆
- 理解变体：思考如何处理”最短”、”恰好”等不同条件
- 多语言实现：用不同语言实现，加深理解
💡 提示：滑动窗口是大厂面试的高频考点，务必熟练掌握！建议多做相关题目，形成直觉。