今天聊Hot100第7题题号3的“无重复字符的最长子串”。这道题在LeetCode上的热度常年居高不下Hot100榜单里它是滑动窗口类题目的入门代表也是很多公司笔试面试的常客。毫不夸张地说弄懂这一题等于把“滑动窗口”这个概念真正吃透了一半。适合所有刷题新手把它当成第一道双指针入门题来啃也适合已经刷过一遍但没过几天又忘了怎么写的同学用来复盘。这题的题面相当短给你一个字符串 s请你找出其中不含有重复字符的最长子串的长度。注意是“子串”不是“子序列”子串要求连续。比如 s abcabcbb答案是 3因为最长无重复子串是 abc长度 3s bbbbb答案是 1s pwwkew答案是 3对应 wke 或 kew注意不是 pwke因为那是子序列而不是连续子串。如果你第一次见这个题第一反应肯定是暴力三重循环枚举左端点、枚举右端点、再检查这一段有没有重复字符。这个方法当然能算出正确答案但等你提交之后就会发现LeetCode 给出的数据范围让暴力解法直接运行到天荒地老。这篇文章我会把从暴力思路到滑动窗口的完整演进过程讲清楚再把哈希表版本和数组版本的细节对比、常见 Bug、面试追问一次说完。1. 题目拆解从暴力到滑动窗口的必然演进1.1 先明确“子串”和“无重复”的含义很多人栽在“子串”和“子序列”的区别上。子串必须是从原字符串里连续截取的一段字符比如 abcabcbb 里第 0 位到第 2 位是 abc这是一个子串但第 0 位、第 2 位、第 5 位拼起来组成 acb这就不是子串因为中间跳过了字符。这道题里要求的“最长子串”天然就和“连续性”绑定这个约束决定了我们只能用连续窗口去扫描而不是做一些全局的组合判断。“无重复字符”也很好理解就是窗口内的每个字符都只能出现一次。有人一开始会把问题想成“统计每个字符最后出现的位置然后找最远的”也有人会想成“用 set 维护一段窗口内的字符集合”这两种思路在方向上都是对的但真正高效的做法需要结合“连续、滑动”这两个特性一起考虑。我建议你拿到题先不要看题解花 5 分钟在纸上写出暴力解法。写暴力不是为了提交通过而是为了让你体会“哪些重复计算可以去掉”。你看暴力枚举左端点 i 和右端点 j然后用一个 set 检查 s[i..j] 有没有重复字符这样的循环主体是 O(n^3)。这里面的核心浪费在于每次窗口扩展一个字符时我们明明可以从上一个窗口的状态继续推导却非要重新遍历整段。这就是后面双指针出现的根本原因。1.2 暴力解法为什么会超时一个具体的复杂度拆解假设 n 是字符串长度。暴力做法的时间复杂度是 O(n^3)因为 i 有 n 种选择j 有 n-i 种选择每次又要对长度为 j-i1 的窗口做一遍重复检查。LeetCode 这种题的数据范围一般在 5×10^4 左右也就是 50000 个字符。我们来算一笔账50000^3 是 1.25×10^14 次操作假设你的电脑每秒能跑 10^8 次简单操作那也需要 1.25×10^6 秒大概 14 天半。你在笔试里提交暴力解法服务器根本不可能等你跑完。就算退一步有些同学想到“优化一下不用每次都检查整段边扩边检查”把内层检查变成 O(1) 的 set 查询时间复杂度降到 O(n^2)50000^2 2.5×10^9 次操作每秒 10^8 也需要 25 秒左右。LeetCode 的判题时间通常只有一两秒所以 O(n^2) 依然过不了。想要通过必须压到 O(n) 级别。这时候你自然会想到能不能用两个指针维护一个窗口让 right 指针一直往右扩展left 指针只在必要时收缩这个思路就是“滑动窗口”也就是这道题的标准解法。字符串类问题里几乎所有“找满足某条件的最长子串/子数组”的题目都可以套这套思路。2. 滑动窗口的完整设计与核心原理2.1 窗口扩容与收缩的判定逻辑滑动窗口的基本框架不复杂维护 left 和 right 两个指针左闭右开或左闭右闭都可以我习惯用左闭右闭因为这样窗口长度直接等于 right - left 1。每次 right 向右移动一格把新字符加入窗口加入之后检查窗口里是否出现重复字符如果出现了就把 left 向右移动直到重复消失。在这个过程中不断用窗口长度更新答案。以 s abcabcbb 为例手动演算一遍你就能理解这套逻辑。初始 left0right0窗口为 a。right 继续扩展为 ab、abc都没有重复。当 right 走到下标 3 也就是第二个 a 时窗口变成 abca里面出现重复于是 left 开始右移。先变成 bca仍然包含两个 a 吗不包含因为 left 已经跳出了第一个 a窗口变成了 bca没有重复此时长度为 3。继续扩展right 到下标 4 的 b窗口 bcab 出现重复left 又移到下标 3窗口变成 cab长度为 3。right 继续到下标 5 的 c窗口 cabc 有重复left 移到下标 4窗口 abc长度 3。以此类推全程最大长度就是 3。这里有一个关键细节left 每步只移一格是一种可行的做法用集合记录窗口内有哪些字符时就必须这样一步步地删字符。但如果在 set 之外再额外记录每个字符最后一次出现的下标就可以让 left 直接跳到重复字符上一次出现位置的后一位省去中间那些必然无效的移动。面试时如果你能主动写出这个“跳跃式”版本会比只会用 set 慢慢删的答案好很多。2.2 数据结构选择的取舍哈希集合、哈希表还是数组确定滑动窗口思路之后还面临一个数据结构选择问题。哈希集合 HashSet 最直观它只关心“当前窗口里有哪些字符”扩展字符时先查是否已在集合中重复就把集合里的旧字符一个个删除。哈希表 HashMap 更进一步它除了记录字符是否出现还记录每个字符最后一次出现的位置这样遇到重复时 left 可以直接跳到 last1而不是一步步挪。数组则是工程上最狠的优化因为字符的码点范围有限可以用 int[128] 或 int[256] 直接按下标访问。三者在时间复杂度上都是 O(n) 的但常数差别很大。哈希集合和哈希表底层有哈希计算、冲突处理尤其是当测试数据量大时内存访问不连续缓存命中率低。而数组记录方式简单粗暴last[c] 最近一次出现该字符的下标每次访问都是直接寻址。我在本地用随机长字符串测过数组版比 unordered_set 版快 3 到 5 倍这在 LeetCode 上体现为时间分布更靠前。你可以这样理解哈希集合是为了“知道窗口里有没有这个字符”哈希表是为了“知道这个字符上次出现在哪”数组则是把 map 的键变成字符码点用连续内存换掉哈希表的随机存储。实际工程里第三种方案在“字符集较小且固定”的场景下非常常用比如只处理 ASCII 字符时。3. 代码实现与参数细节3.1 C 主解法逐行拆解下面是我在实际刷题时维护的模板版本用 vector 数组记录每个 ASCII 字符最后一次出现的下标初始为 -1 表示还没出现过。class Solution { public: int lengthOfLongestSubstring(string s) { int n s.length(); int left 0, ans 0; vectorint last(128, -1); for (int right 0; right n; right) { int idx s[right]; if (last[idx] ! -1) { left max(left, last[idx] 1); } last[idx] right; ans max(ans, right - left 1); } return ans; } };有几个地方特别容易理解错。第一为什么 left 要取max(left, last[idx] 1)而不是直接left last[idx] 1因为 left 可能因为更早的一次重复已经移动到了一个较大的位置如果直接跳到当前重复字符的上一次出现位置之后left 反而可能回退。回退就意味着窗口里会出现已经被排除掉的重复字符答案就可能错误。经典的例子是 s abba处理到最后一个 a 时如果直接把 left 设为上一次 a 出现位置的后一位也就是 1left 就会从 2 退回 1这绝对不对。所以必须用 max 保证 left 单调不减。第二为什么要先查 last 再更新 last因为我们要查找的是“这个字符在当前字符位置之前最后一次出现的位置”如果把当前字符的 last 先更新成 right再回头查 last就会把刚写入的自己当成重复字符逻辑就乱了。顺序一定是先查、再更新。第三ans 的更新放在 last[idx] right 之后这样当前字符已经被正确纳入窗口窗口长度 right - left 1 才能包含它。有些新手习惯先更新 ans 再更新 last在某些情况下也能跑对但会留下隐患不如固定这个顺序。3.2 Java 与 Python 的实现差异Java 版本和 C 几乎可以一一对应只是数组填充时需要手动赋初值class Solution { public int lengthOfLongestSubstring(String s) { int[] last new int[128]; Arrays.fill(last, -1); int left 0, ans 0; for (int right 0; right s.length(); right) { char c s.charAt(right); if (last[c] ! -1) { left Math.max(left, last[c] 1); } last[c] right; ans Math.max(ans, right - left 1); } return ans; } }Python 版本我一般用字典因为 Python 字符串默认就是 Unicode字符范围不一定是 ASCII用数组处理纯 ASCII 测试数据可以但遇到中文或 emoji 就得另想办法。字典版写法class Solution: def lengthOfLongestSubstring(self, s: str) - int: last {} left 0 ans 0 for right, ch in enumerate(s): if ch in last: left max(left, last[ch] 1) last[ch] right ans max(ans, right - left 1) return ansPython 用字典的好处是天然支持 Unicode 字符坏处是哈希访问常数比较大。如果题目限定输入只包含小写字母或其他 ASCII 字符可以换成一个长度 128 的列表速度能快不少。但说实话在 Python 里这点性能差距在 LeetCode 判题机上影响不大绝大多数情况下字典版就够了。我自己的习惯是先默写出数组版 C 解法因为它最快、最简单、没有任何动态内存分配面试时写起来非常流畅等聊到边界情况或者面试官追问“如果字符范围不固定怎么办”再切换到哈希表版本。这样既展示了基础能力又展现了思考深度。4. 踩坑记录与高频面试追问4.1 实际提交中常犯的四个错误这个题代码量不大但出错的点极其典型。我把这段时间看到的、自己也踩过的坑整理成了速查表。错误现象原因正确做法输入为空串返回 0输出却为 1ans 初始化为 1ans 应初始化为 0因为最长子串长度不可能超过 0只考虑小写字母数组开到 26遇到空格或大写字母越界主观假设字符集按题目说明使用 128 或 256统一覆盖 ASCII遇到重复字符时 left 直接用 last[c]1 而不是 max没考虑 left 已经因为更早重复向后移过使用left max(left, last[c] 1)更新 last 之后再检查 last导致判断永远重复顺序写反先判断 old last[c]再写入 last[c] right空串和单字符是最容易翻车的两个边界。空串要返回 0单字符要返回 1。用数组版本时如果不开满 128 个位置遇到像 这样的空格输入会直接越界面试官还特别爱拿这种看似无厘头的输入来试探你。另外不知道你有没有注意到使用vectorint last(128, -1)时字符会被隐式转换成 int 码点比如大写字母 A 对应 65空格对应 32。只要数组长度大于所有可能的码点就不会出问题。C 里 char 可能是带符号的如果直接用 char 当下标且字符码点超过 127会出现负数下标越界所以稳妥做法是只处理 ASCII 128 范围内的字符或者显式转换成 unsigned char。4.2 面试官常见的五个追问变体如果你把基础解法写得飞快面试官很容易追加几个变形问题。我就被连环问过一轮在这里一起整理出来。第一问如果字符串只包含小写字母能不能进一步优化当然可以除了数组版本还可以用位运算。用一个 32 位整数 mask每个 bit 代表一个小写字母是否出现过。但要注意这里只能记录“存在与否”不能记录“最后一次出现的位置”所以位运算适合和标准双指针配合用来 O(1) 判断窗口里是否有重复字符。这个技巧在面试中属于“超预期答案”写出来很加印象分。第二问如果题目要求返回最长无重复子串本身而不是只返回长度怎么做解法思路不变只是每次更新 ans 时额外记录此时的 left 和 right最后用s.substr(bestLeft, maxLen)返回子串。这个变体经常作为第二小问出现代码量增加不多但考察你是否理解窗口边界。第三问如果不限字符集比如字符串包含中文、emoji怎么做C 里 char 只能表示单字节处理不了这类字符Java 的 String 基于 UTF-16一个 emoji 会占用两个 char直接按 char 扫描会把 emoji 拆成两半。Python 的字典方案天然按 Unicode 码点处理最省事。这个问题很少直接从代码角度问但如果你想展示工程经验可以提一句“真实生产环境要考虑的是码点而不是 char”。第四问把“无重复字符”改成“最多 k 个不同字符”求最长子串怎么做这就是 LeetCode 340思路是维护窗口内字符种类数当种类数超过 k 时收缩 left直到窗口内的不同字符数量回到 k。核心模板和本题几乎一致只是把“重复与否”的判断换成“不同字符数量是否超过阈值”。第五问把“子串”改成“子数组”元素从字符换成整数这题还成立吗成立因为整数的可比较性和字符一样窗口维护方式完全不变。题目换成“无重复元素的最长子数组”你看一眼就会做了。5. 刷题方法论从这道题看 Hot100 的整体复习价值5.1 这道题关联的题目网络Hot100 榜单不是简单拼凑的题单它的编排实际上按知识点形成了网络。“无重复字符的最长子串”属于“滑动窗口”这一簇这簇题在面试里出现频率极高。和它关联的常考题目有题目关联点建议复习方式76. 最小覆盖子串同样是双指针滑动窗口但要求窗口满足包含关系收缩逻辑更复杂理解“窗口长大了再收缩”的框架424. 替换后的最长重复字符维护窗口内最大频次字符推导出需要替换的字符数结合数组统计字符频次1004. 最大连续 1 的个数 III允许翻转 k 个 0本质是窗口内 0 的数量不超过 k直接套模板改收缩条件159. 至多包含两个不同字符的最长子串维护窗口内不同字符数不超过 2高难度变体适合周赛前练习340. 至多包含 K 个不同字符的最长子串159 的进阶版吃透这题窗口类就稳了我的建议是刷完这道题之后用一周时间把上面几道题集中刷完。它们之间相似度很高区别基本只是“窗口收缩条件”的微调。集中刷的好处在于你能在短时间内形成肌肉记忆而不是今天做一题、下周做一题每次又要重新理解一遍框架。5.2 我刷 Hot100 的做题节奏与标记策略关于刷题本身我想分享一点个人的习惯。我在刷 Hot100 时会给每道题打三个标签之一“模板题”“要重刷”“理解不透”。“无重复字符的最长子串”就属于典型的模板题它不仅本身常考更重要的是它是理解其他滑动窗口题的钥匙。我的做法是第一次做先不看解答限时 15 分钟。能 AC 就标记“模板题”隔 5 天重做一遍没有 AC 就看题解看懂后过 3 天和 7 天各重做一遍。一道题要连做三轮都稳定 AC我才会把它从“要重刷”改成“已掌握”。很多题第一遍做的时候似懂非懂第二遍照样卡住第三遍才真正内化。这不是浪费时间恰恰是对抗遗忘曲线最有效的笨办法。在时间分配上我建议不要把 Hot100 的 100 道题平均用力。滑动窗口、动态规划、二叉树这三块权重最高值得投入更多时间。像“无重复字符的最长子串”这种基础题花 30 分钟彻底搞懂并做完变体比泛泛刷 5 道同类题更有价值。我在实际使用中发现很多面试者能背出滑动窗口模板但被问到“为什么 left 要取 max”就卡壳。原因就是刷题时只记住了代码没有理解每一步背后的约束。这道题正好是一个极好的自检样本如果你能不用调试工具纯靠思路在纸上演算一遍 “abba” 的完整过程并解释清楚 left 为什么从 0 变到 2 再变到 3那你才算是真的吃透了。所以最后再分享一个小技巧学完这道题后你可以在 LeetCode 里开启“随机一题”模式做三到四次类似题每次都用固定模板去套不再看题解。做到第三次的时候你会发现写这道题的代码几乎不经过大脑手指直接就出来了。那个状态就是“这道题真正属于你”的状态。