无重复字符最长子串：滑动窗口与哈希表优化全解析

1. 题目解读：无重复、连续、一刀切，哪个才是命门

LeetCode Hot100 刷到第 7 题，撞上的是原题第 3 题“无重复字符的最长子串”。这题在 Hot100 里的地位不用多说，属于那种“面试官闭着眼睛也能从题库里点出来”的常客。题目很短：给定一个字符串s，请你找出其中不含有重复字符的最长子串的长度。

我第一次刷这道题的时候，注意力全放在“无重复字符”上，脑海里蹦出来的第一反应是“用个哈希表去重”。但真正让你翻车的不是去重，而是“子串”两个字——子串必须是连续的。这意味着你不能像处理子序列那样跳着取字符，所有的合法答案都是原字符串中某一段连续切割出来的。

拿官方示例消化一下：

• s = "abcabcbb"，答案是 3，对应"abc"。
• s = "bbbbb"，答案是 1，对应"b"。
• s = "pwwkew"，答案是 3，对应"wke"或"kew"。

注意最后这个例子非常关键："pwke"是一个子序列，跳过了中间的w，但它不是子串，所以不算数。题目只要长度，不要具体子串，这已经算是手下留情了——很多大厂面试会让面试官追问“你把子串本身打印出来”。

还有一个容易忽略的点：题目默认字符集是 ASCII 还是 Unicode？LeetCode 原题没有明说，但测试数据用的是可见 ASCII 字符。这意味着"a b"中间的空格、"ab!c"里的标点，全都算合法字符。实测下来，大小写也要严格区分，"aA"是两个不同字符，长度是 2，不是 1。

如果你把题设里的“字符”想象成幼儿园小朋友排队，题目就变成了：找出最长的一段队伍，要求这一段里没有两个小朋友长得一模一样。任何一个小朋友重复出现，这段队形就得从右边裁掉一块，或者从左边挪走前面的人。

这个认知很重要，因为后面理解滑动窗口的时候，你会发现它本质上是两个指针在字符串上“拉链式”地滑动，左边指针负责裁掉重复部分，右边指针负责扩展不断引入新字符。

2. 暴力的天花板：O(n³) 是怎么来的，又为什么必挂

在没有接触过滑动窗口之前，绝大多数人的第一直觉是暴力枚举。写起来也很顺手：把所有子串都列出来，逐个检查是否包含重复字符。

2.1 暴力解法的三层循环

暴力解的逻辑可以用一句话概括：枚举起点i，枚举终点j，然后检查s[i..j]这个区间内的字符是否有重复。

public int lengthOfLongestSubstring(String s) { int n = s.length(); int ans = 0; for (int i = 0; i < n; i++) { for (int j = i + 1; j <= n; j++) { if (allUnique(s, i, j)) { ans = Math.max(ans, j - i); } } } return ans; } private boolean allUnique(String s, int start, int end) { Set<Character> set = new HashSet<>(); for (int k = start; k < end; k++) { if (set.contains(s.charAt(k))) { return false; } set.add(s.charAt(k)); } return true; }

这个版本的时间复杂度是 O(n³)：两层循环枚举子串，第三层循环检查唯一性。空间复杂度 O(min(n, m))，也就是哈希表占用的空间。

2.2 复杂度估算：n=5×10⁴ 的时候会怎样

LeetCode 原题给的数据范围是0 <= s.length <= 5 * 10^4。用 O(n³) 算一下，最坏情况是 1.25 乘以 10 的 14 次方级别的字符访问量，这个数量级在现代计算机上跑完可能要几分钟到几十分钟，必然超时。

如果你稍微聪明一点，把第三层循环合并到第二层里，一边枚举终点一边维护哈希表，能优化到 O(n²)：

public int lengthOfLongestSubstring(String s) { int n = s.length(); int ans = 0; for (int i = 0; i < n; i++) { Set<Character> set = new HashSet<>(); for (int j = i; j < n; j++) { if (set.contains(s.charAt(j))) { break; } set.add(s.charAt(j)); ans = Math.max(ans, j - i + 1); } } return ans; }

这个版本用break提前终止内层循环，避免了重复扫描整个子串，时间复杂度降到 O(n²)。但当 n 是五万的时候，O(n²) 依然意味着大约 25 亿次操作，在 LeetCode 的评测机上照样超时。

从 O(n³) 到 O(n²) 是在“同一个思路上打补丁”，真正的拐点是你意识到：区间检查过程中产生的大量信息可以被复用。你在枚举i=0, j 从 1 走到 n的过程中，已经知道[0..3]是干净的，为什么枚举i=1的时候还要重新从空集合开始积累？这就是后来滑动窗口能砍掉一层循环的根本原因——把重复的扫描变成连续的滑动。

我当时在这个暴力阶段折腾了不到十分钟，就确认一条经验：所有“最长子串”“最短子串”类的题目，第一步不要去写暴力，先去想能不能用双指针维护一个可变窗口。这不是什么高深技巧，而是这类题型的通用套路。

3. 滑动窗口基线版：让两个指针像拉链一样收敛

滑动窗口这个名字听起来高级，实际上就是维护两个下标left和right，它们圈定当前考察的子串区间[left..right]。right每次往右走一步，引入一个新字符；left根据情况决定是否往右移动，直到窗口内再次没有重复字符。这就像一个拉链：右齿不断前进，左齿遇到阻力时先退让，两边的距离就是当前窗口的长度。

3.1 关键观察：重复字符是怎么被发现的

假设当前窗口[left..right]内没有任何重复字符，此时right向右走一步，新字符是c。现在只有两种可能：

1. c不在窗口内：窗口变长，更新答案。
2. c在窗口内：为了让窗口恢复“无重复”状态，需要不断把left向右移，同时把移出的字符从集合里删掉，直到把那个与c相同的旧字符移出窗口为止。

这里有个容易搞混的细节：left移动的次数不是 1，而是可能很多次。为什么？因为重复字符可能在窗口中间。比如窗口是"abcd"，新来的是'd'，你需要把left从a一路移到d后面，移出的字符包括a、b、c、d，总共 4 步。所以基础版滑窗的内部会有一个while循环，这个循环做的事情就是“收缩窗口”。

3.2 基线版代码与逐轮演示

用HashSet作为“窗口内字符集合”，是最直观的写法：

public int lengthOfLongestSubstring(String s) { Set<Character> set = new HashSet<>(); int n = s.length(); int left = 0; int ans = 0; for (int right = 0; right < n; right++) { char c = s.charAt(right); // 如果窗口内已经有 c，就一直收缩 left while (set.contains(c)) { set.remove(s.charAt(left)); left++; } // 此时窗口内一定没有 c，放心加入 set.add(c); ans = Math.max(ans, right - left + 1); } return ans; }

拿s = "abcabcbb"手动走一遍，你会看到窗口的状态是这样变化的：

这里最容易看错的点是 right=6 的时候：窗口是从[abc]开始，新字符b。left移动一次，从a跳到b（移出a），此时窗口变成[bc]，但窗口里还有那个最右侧的b吗？等一下，我重新推一遍。

快照应该这样记：right=6 时，s[6] = 'b'。当前窗口其实是 right=5 结束后留下的[bca]吗？不对，用上面的表格看，right=5 结束时窗口是[abc]（即索引 3,4,5 的 a,b,c）。此时 right=6 的字符 b 与索引 4 的 b 重复，left 需要右移。先移出索引 3 的 a，窗口变成[bc]（索引 4,5）。窗口里仍然有索引 4 的 b，继续循环，left 移到 4，移除 b，窗口变成[c]（索引 5）。然后 set 里没有 b 了，加入 s[6]，窗口变成[cb]（索引 5,6），长度 2，所以 ans 保持 3。表格里我写的是从[abc]到[cb]，这个没毛病，但中间经历的两次循环要说清楚。

细心的读者会发现，这个过程中每个字符被加入集合一次、被移除集合最多一次。所以虽然内部有while，但总操作次数是 O(n) 级别的。当一个字符被left移出窗口后，如果right在后面的某一步又遇到了它，它会被重新加入集合——注意，一个字符可以在不同时刻多次进入窗口，比如"abba"里的'b'就会进出好几次。

这个基线版本的优点是逻辑极其清晰，几乎不会写错。缺点是while循环在极端情况下（比如全字符串都是同一个字符）会频繁收缩，但依然不会超时，因为总体线性。空间复杂度最坏 O(n)（当整个字符串无重复时，set装下所有字符）。

4. 哈希表位置优化：从“逐步收缩”到“直接跳跃”

基线版能 AC（Accepted），但面试官大概率会追问一句：“能不能再优化？”这时候你要拿出HashMap版本。

4.1 从 HashSet 到 HashMap：省掉的不只是 while 循环

思路转变在一个细节上：基线版用HashSet只记录了“窗口内有什么”，没记录“窗口内每个字符在哪个位置”。当遇到重复字符时，它只能一个字符一个字符地往外挪，直到挪到那个重复字符的下一位。

如果用HashMap<Character, Integer>记录每个字符最近一次出现的位置，那么当right遇到一个已经出现过的字符c时，你可以直接读出c上一次出现的位置lastIndex。此时，left最少也得跳到lastIndex + 1，因为lastIndex那个位置以及它左边的所有字符，都不可能再出现在新的最长无重复子串里了。

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

这段代码的精髓是left = Math.max(left, map.get(c) + 1)。刚看到这一行的人很容易犯迷糊：为什么不是left = map.get(c) + 1，非要套一个Math.max呢？

4.2 为什么必须 Math.max，以及 tmmzuxt 的真实教训

原因很简单：left只能向右走，不能向左退。map.get(c)记录的是“字符 c 上一次出现的位置”，这个位置可能远在当前left的左边。如果直接拿它更新left，窗口的左边界反而会回退，导致窗口包含已经处理过的无效区域。

经典的翻车用例是s = "tmmzuxt"。前两个字符t和m都是第一次出现，map里存着t -> 0, m -> 1。遇到索引 2 的m重复，left跳到 2，窗口是[mzu]的方向。继续向右，遇到x、t，最后到索引 6 的t。此时map.get('t') = 0，如果不用Math.max，left会被更新成 1，窗口变成[mmzuxt]？不对，left 回退到 1 就会让窗口里包含索引 1 的m和索引 2 的m，两个m重复，答案算错。

用了Math.max(left, 1)之后，因为当前left已经是 2，比 1 大，所以left保持不变。窗口继续合法地向右推进，最终答案 4，对应"mzuxt"或"t"开头的那段。这个用例我在本地跑过，去掉Math.max会输出 5，一眼就能看出错误。

这个版本的时间复杂度依然是 O(n)，但由于省去了内层while循环，实际常数更小。空间复杂度同样是 O(min(n, m))，m是字符集大小。因为题目限定可见 ASCII 字符，m最大不过 128，所以你可以进一步把HashMap换成定长数组：

public int lengthOfLongestSubstring(String s) { int[] last = new int[128]; Arrays.fill(last, -1); int n = s.length(); int left = 0; int ans = 0; for (int right = 0; right < n; right++) { char c = s.charAt(right); if (last[c] >= left) { left = last[c] + 1; } last[c] = right; ans = Math.max(ans, right - left + 1); } return ans; }

数组版本的空间复杂度是严格的 O(1)，因为int[128]大小固定。判断条件为什么是last[c] >= left而不是last[c] != -1？还是同样的道理：一个字符确实出现过，但它可能是在当前left左边出现的，早就被移出窗口了，此时它对当前窗口不构成威胁，不需要触发left移动。只有在last[c]仍然位于窗口内（即>= left）的时候，才说明窗口内出现了重复。

我第一次写数组版本时，就是只判断!= -1，结果在"abba"上翻车。后面走到'a'时，last['a'] = 0，而left已经是 2，窗口是[b, a]（索引 2 的 b 和索引 3 的 a），里面没有a的重复，但我被旧索引误导，把left回退到了 1，白白把答案算大。加一个>= left的判断就药到病除。

5. 提交实录：四个坑，每一种都让人血压升高

这题看着简单，提交的时候坑一个接一个。我前后提交过好几版，把踩过的坑总结成四条，你照着躲就行。

5.1 死循环与漏删：基线版编码时的两个大坑

第一个坑是忘了在收缩窗口时把字符从set里删掉。有的人写while收缩时，只把left往右移，但不对set执行remove，结果集合越来越大，set.contains(c)永远为真，代码陷入死循环。代码逻辑上，“移出窗口”和“从集合中删除”必须是原子操作，你移left指针的同时，必须删除s.charAt(left)。

第二个坑是更新答案的位置。有人把ans = Math.max(ans, right - left + 1)放在while收缩之前，这时窗口可能还包含重复字符，算出来的长度偏大，而且后面又不会自动纠正，因为窗口收缩后ans的更新可能要等到下一轮。标准做法是先收缩，确认窗口合法，再计算长度。

5.2 数组代替哈希表：优化到真正的 O(1) 空间

这里有个面试官爱考的细节：为什么能用int[128]？因为题目中的字符是 ASCII 码，范围 0 到 127。如果你用int[256]也没问题，覆盖扩展 ASCII 码。但如果你在比赛里遇到包含中文的字符串，char的范围远不止 256，固定数组就不够用了，还是得回到HashMap。

用数组时，初始化为-1表示“从未出现过”，这个初始值选得非常巧妙。如果初始化为 0，你没法区分“索引 0 出现过”和“从未出现”。-1让last[c] + 1在首次遇到时正好是 0，和left的初始值对齐，不用额外处理。

5.3 边界测试：空串、单字符与中文输入

LeetCode的测试用例里永远有边界。空串s = ""应该返回 0；长度为 1 的字符串应该返回 1。你写的代码只要初始ans = 0，并且for循环在空串时直接跳过，这两个用例自然通过。但单字符用例要小心：如果字符串只有一个字符且它不是重复的，循环结束后ans会被正确更新为 1，不需要额外 if 分支。

中文输入测试建议自己补一下。虽然 LeetCode 原题不涉及中文，但如果你面试时被要求扩展到任意 Unicode 字符，char在 Java 里是 UTF-16 的，可能一个中文字符占一个char（常见汉字）也可能占两个（生僻字、emoji）。用HashMap<Character, Integer>时，遇到双字节字符会拆开处理，逻辑上会出错。更稳妥的写法是把输入先按 Unicode 码点切分，或者改用Map<Integer, Integer>存codePoint。这块属于进阶话题，刷题阶段了解即可，真遇到再处理。

5.4 返回子串本身怎么办

很多时候面试官会改需求：“不是返回长度，是返回那个最长子串。”这时候你需要在滑动过程中记录窗口最大时对应的起点：

public String longestUniqueSubstring(String s) { Map<Character, Integer> map = new HashMap<>(); int left = 0; int maxLen = 0; int start = 0; for (int right = 0; right < s.length(); right++) { char c = s.charAt(right); if (map.containsKey(c)) { left = Math.max(left, map.get(c) + 1); } map.put(c, right); if (right - left + 1 > maxLen) { maxLen = right - left + 1; start = left; } } return s.substring(start, start + maxLen); }

核心差别是每次窗口扩大时，不仅要更新maxLen，还要顺手记录当时的left。这个改动很小，但很多人到了现场会卡住，因为平时只练了返回长度的版本。

6. 同源变形题：Hot100 里的滑动窗口四连

刷完第 3 题，你其实已经掌握了 Hot100 里一大批同源题目的骨架。我这里点几个，方便你后续一起打包刷掉。

6.1 同源题目与通用模板

• LeetCode 76 最小覆盖子串：两个字符串，要求你用s的一个子串覆盖t的所有字符。核心是维护一个“欠账表”，right扩大窗口时还账，窗口满足需求后left收缩寻找最短。这题比第 3 题多一个“覆盖计数”的概念，但窗口框架完全一致。
• LeetCode 438 找到字符串中所有字母异位词：固定窗口长度的滑动窗口。窗口长度恒等于p的长度，每滑动一步检查窗口内的字符频率是否和p完全一致。和第 3 题不同，这里窗口大小是固定的，只需要判断“频率是否匹配”。
• LeetCode 567 字符串的排列：和第 438 题的思路几乎一样，区别只是问你“是否存在”而不是“返回所有位置”。这个题目经常被拿来作为第 76 题的前置练习。

这类题的通用模板可以抽象成下面这个框架：

// 通用滑动窗口模板（伪代码） int left = 0; for (int right = 0; right < s.length(); right++) { // 1. 将 s[right] 加入窗口，更新相关状态 // 2. 当窗口不再满足条件时，收缩 left，直到重新满足 // 3. 在窗口满足条件后，更新全局答案 }

把第 3 题往里套：状态是“字符集合”，窗口条件变成“集合内无重复”，答案在每次窗口满足条件后取最大长度。把第 76 题往里套：状态变成“各字符的欠款计数”，条件变成“所有欠款清空”，答案在窗口满足条件后取最小长度。骨架不变，变的只是状态定义和条件判断。

6.2 建议的刷题顺序与练习节奏

我的个人建议是：先把第 3 题的三个版本（基线版、HashMap 版、数组版）都写到滚瓜烂熟，最好能达到闭着眼在白板上写出来的程度。然后再刷 567 和 438，把固定窗口的套路练熟。最后啃 76，因为它是可变窗口里最复杂的一种，需要你同时管理两个哈希表或者两个数组的频率变化。刷完这四题，你在处理“子串 + 重复/覆盖 + 最值”这个组合时，基本可以秒出思路。

LeetCode Hot100 这个题单里面，滑动窗口题目出现频率不低。除了上面四道，还有像是“滑动窗口最大值”这种用单调队列配合的题目，属于进阶变形。但核心逻辑始终是那个模板：right负责干活，left负责擦屁股，窗口永远维护一个合法状态。

我在实际刷题中养成的习惯是：写代码之前先在草稿纸上把窗口的推进过程画一遍，特别是那种重复字符出现在窗口正中间的场景，画完再写能让你的边界条件一次写对。这道题的三个版本，我大概每隔两周就会重新写一遍，不是为了通过率，而是因为它是滑窗思想最浓缩的标本，偶尔回炉总能有新体会。