Hot 100 --- 无重复字符的最长子串

本文概览：本文以LeetCode经典题目"无重复字符的最长子串"为例，从暴力解法入手，逐步优化到滑动窗口解法，系统讲解如何利用窗口滑动和哈希表快速跳过重复字符，将时间复杂度从 O(n²) 优化到 O(n)

---

一、题目

二、题目分析

给定一个字符串 s，找出其中不含有重复字符的最长子串的长度

目标：返回无重复字符子串的最大长度

核心概念：子串 vs 子序列

• 子串：字符串中连续的字符序列，如 "abc" 是 "abcde" 的子串
• 子序列：不要求连续，只需保持相对顺序，如 "ace" 是 "abcde" 的子序列但不是子串

本题求的是子串，要求字符必须连续

思路概览

Java实现代码如下

public int lengthOfLongestSubstring(String s) {
    int n = s.length(), ans = 0;
    Map<Character, Integer> map = new HashMap<>();
    for (int end = 0, start = 0; end < n; end++) {
        if (map.containsKey(s.charAt(end))) {
            start = Math.max(map.get(s.charAt(end)), start);
        }
        ans = Math.max(ans, end - start + 1);
        map.put(s.charAt(end), end + 1);
        if(n - star <= ans)
            break;
    }
    return ans;
}

思路简要说明

1. 滑动窗口：用 start 和 end 两个指针维护一个窗口，表示当前无重复字符的子串

2. 遇到重复字符时跳过：当 end 指向的字符已经在窗口中出现过，直接将 start 跳到重复字符的下一个位置，而不是逐个右移

3. 哈希表加速查找：用 HashMap 记录每个字符最后出现位置的下一个位置，实现 O(1) 的重复检测和跳转

三、思路详解

暴力解法入手

最自然的想法是：枚举所有可能的子串，检查每个子串是否含有重复字符，记录最长的那个

具体来说，对于每个起始位置 i，从 i 开始逐个向右扩展子串，每加入一个字符就检查是否重复，一旦重复就停止扩展，记录当前长度

显然可以得出以下结论

• 时间复杂度：O(n²)，对每个起始位置都要向右扫描
• 核心瓶颈：当发现重复字符时，我们只把起始位置右移一位重新开始扫描，但前一次扫描中已经确认无重复的那部分子串又被重新检查了一遍，做了大量无效计算
• 关键思考：当发现重复字符时，能否直接跳过已经确认无重复的部分，而不是只右移一位？

滑动窗口解法

思路分析

暴力解法的问题在于：每次发现重复后，start 只右移一位，导致大量已经确认无重复的区域被重复扫描

我们来换一个视角：把当前正在考察的子串看成一个窗口，这个窗口在字符串上从左往右滑动

• 窗口的左边界是 start，右边界是 end
• end 每次向右扩展一个字符，试图把新字符加入窗口
• 如果新字符没有在窗口中出现过，窗口直接扩展，子串长度 +1
• 如果新字符已经在窗口中出现过，说明出现了重复，此时我们不需要把 start 逐个右移，而是直接把 start 跳到窗口中重复字符的下一个位置

为什么可以直接跳？我们用一个具体的例子来看

以字符串 abccefx 为例

窗口从左往右扩展：

• [a] b c c e f x — 加入 a，无重复
• [a b] c c e f x — 加入 b，无重复
• [a b c] c e f x — 加入 c，无重复
• [a b c c] e f x — 尝试加入第二个 c，发现重复！

此时窗口内的 a b c c 包含了两个 c，不满足"无重复字符"的条件。窗口需要缩小，也就是把 start 右移

那 start 右移多少？如果只右移一位，变成 a [b c c] e f x，仍然有两个 c，还是重复。再右移一位变成 a b [c c] e f x，还是重复。继续右移变成 a b c [c] e f x，此时才无重复

也就是说，我们需要把 start 一直移动到第一个 c 的下一个位置，才能让窗口内不再包含那个导致重复的旧 c

所以核心逻辑就是：下一个要加入窗口的字符如果在窗口中已经存在，start 就直接跳到窗口中该字符第一次出现位置的下一个，中间的位置都不用试，因为那些窗口仍然包含那个重复字符

如何快速知道重复字符的位置？

使用 HashMap，键为字符，值为该字符下一次可以出现的位置（即 end + 1）。这样当发现重复时，直接从 map 中取出值赋给 start 即可

举例说明

以 s = "abcabcbb" 为例

初始：start = 0, end = 0, map = {}, ans = 0

步骤	end	字符	map 中是否存在	start 变化	更新 map	当前窗口	长度	ans
1	0	a	否	start=0	a→1	[a]	1	1
2	1	b	否	start=0	b→2	[a,b]	2	2
3	2	c	否	start=0	c→3	[a,b,c]	3	3
4	3	a	是(a→1)	start=max(1,0)=1	a→4	[b,c,a]	3	3
5	4	b	是(b→2)	start=max(2,1)=2	b→5	[c,a,b]	3	3
6	5	c	是(c→3)	start=max(3,2)=3	c→6	[a,b,c]	3	3
7	6	b	是(b→5)	start=max(5,3)=5	b→7	[c,b]	2	3
8	7	b	是(b→7)	start=max(7,5)=7	b→8	[b]	1	3

最终结果为 3

为什么 start 要取 Math.max？

首先要明确一个关键点：map 存的是从字符串开头到 end 为止，每个字符历史上出现过的所有位置信息，而不是实时只存窗口内的字符。map 只增不删，遍历过的字符都会被记录下来

这就带来一个问题：map 中记录的某个字符的位置，可能已经在当前窗口的左边了，也就是说那个字符已经不在当前窗口中，但我们无法从 map 中分辨出来

如果不取 Math.max，直接用 map.get(...) 赋值给 start，就可能导致 start 向左回退，窗口错误地扩大

举例说明：字符串 abcdeba

• 窗口逐步扩展：[a b c d e] b a，此时遇到第二个 b（end = 5）
• b 在 map 中的值是 2（第一个 b 的下一个位置），start 从 0 跳到 2，窗口变成 a b [c d e b] a
• 继续扩展：a b [c d e b a]，此时遇到第二个 a（end = 6）
• a 在 map 中的值是 1（第一个 a 的下一个位置，这是很久以前记录的）
  如果不取 max：start = map.get('a') = 1，start 从 2 回退到了 1！这显然是错误的，因为位置 0 的那个 a 早就被窗口抛在身后了，当前的 a 和位置 0 的 a 根本不构成重复
• 取了 max：start = Math.max(1, 2) = 2，start 保持在 2 不动，窗口正确：a b c [d e b a]

所以 Math.max 的作用是：确保 start 只能往右走，不能往回退，避免 map 中的旧信息干扰当前窗口的判断

为什么可以用 n - start <= ans 提前结束？

这是一种剪枝优化：当剩余可遍历的字符数量已经不大于当前找到的最大长度时，即使后面所有字符都不重复，也不可能再找到更长的子串了

具体来说：

• n 是字符串总长度
• start 是当前窗口的左边界
• n - start 表示从 start 到字符串末尾还剩多少个字符
• ans 是目前已经找到的最长无重复子串长度

如果 n - start <= ans，说明剩下的字符就算全部能组成一个无重复子串，长度也最多是 n - start，不可能超过当前的 ans。既然不可能再刷新记录了，就没必要继续遍历下去了

举例说明：字符串 abcde，当前 ans = 3（比如已经找到了 abc），start = 2，n = 5

• n - start = 5 - 2 = 3，等于 ans = 3
• 从 start = 2 开始，剩余字符只有 3 个（c d e），即使这 3 个都不重复，最长也只能是 3，不可能超过当前的 ans
• 所以直接 break，提前结束遍历

为什么 map 存的是 end + 1 而不是 end？

因为我们希望 start 跳到重复字符的下一个位置。如果存的是 end，取出后还要 +1；直接存 end + 1，取出后就能直接赋给 start，更简洁

• 时间复杂度：O(n)，end 指针最多遍历一次字符串，start 只会往右跳不会回退
• 空间复杂度：O(min(m, n))，其中 m 为字符集大小，map 最多存储字符集大小个键值对