这次不打算直接丢一个“标准答案”完事我想把这个过程完整拆开。从读完题目到写出最优解中间有哪些纠结和取舍容易踩的坑以及上线后在面试里可能被追问的变体一条条说清楚。这道题是力扣热题100的第4题无重复字符的最长子串。很多人背过滑动窗口模板但换道题又不会了本质上是没搞懂滑动窗口为什么长这样。看完这篇你能独立推导出解法而不是靠背。1. 题目到底在问什么1.1 先看懂示例题目给了一个字符串让你找其中最长的子串要求子串里所有字符都不能重复返回这个长度。比如s abcabcbb最长的不重复子串是abc长度是 3。注意是子串不是子序列。子串要求连续子序列允许跳着取这两个概念混淆的话后面写代码就是灾难。abc在abcabcbb里是连续的三个字符所以是子串如果让你取ac它在原串里虽然存在但中间还隔着b那就是子序列。还有一个关键点题目只要求返回长度不要求返回具体是哪个子串。如果面试官追问“那你能不能把子串也打印出来”代码里要额外维护起点和终点的下标这属于扩展题后面我会讲。1.2 别急着写代码先想清楚两件事拿到这道题我建议你先问自己两个问题。第一暴力解法能不能解当然能。穷举所有子串逐个判断有没有重复字符取最大长度。问题在于复杂度。假设字符串长度是 n子串数量是 O(n²)判断一个子串是否不重复又需要 O(n) 的扫描整体就是 O(n³)。力扣给的数据范围是0 s.length 5 * 10⁴n³ 直接爆炸。有人会说用 HashSet 判断可以把检查降成平均 O(1)但即便如此整体的 O(n²) 还是扛不住 5 万长度的数据。第二有没有冗余计算这是滑动窗口的核心动机。你在检查s[i..j]时如果发现第j个字符重复了暴力做法是让i加 1再从i开始重新枚举j。仔细想一下你已经知道s[i..j-1]是无重复的只是加入s[j]之后才冲突。那下一次循环完全没必要把s[i1..j-1]再从头检查一遍直接复用现有信息就行。这个“复用”的思路区分了新手和老手。2. 从暴力到滑动窗口的核心推导2.1 暴力解法的复杂度推导先给出暴力版 Java 代码作为分析的基线。public int lengthOfLongestSubstring(String s) { int n s.length(); int ans 0; for (int i 0; i n; i) { for (int j i; j n; j) { if (allUnique(s, i, j)) { ans Math.max(ans, j - i 1); } } } return ans; } private boolean allUnique(String s, int start, int end) { SetCharacter 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; }时间消耗在两层枚举加一层扫描上。i和j的组合数量是 n(n1)/2每个组合要扫一遍窗口平均长度大约是 n/3所以复杂度 O(n³) 这个结论不夸张。实际跑一下n 1000的时候就明显卡顿n 50000的时候这辈子等不到结果。这就是为什么必须优化。2.2 滑动窗口的思维演进我想用一句话总结滑动窗口的思路固定右端点让左端点跟着右端点走。想象你有一根可以伸缩的尺子左端点是left右端点是right。一开始left0然后right从 0 开始向右移动。每移动一次right就检查当前窗口s[left..right]是否合法。如果合法说明以right结尾的当前窗口是一个可行解记录长度如果不合法说明s[right]这个字符在窗口里已经出现过了此时要把left往右移动直到窗口重新合法。这里最关键的一步left移动到哪里假设s[right]上一次出现的位置是lastIndex那left至少要跳到lastIndex 1窗口里才可能没有s[right]。同时left只能往右移动不能倒退所以是left Math.max(left, lastIndex 1)。这就是为什么很多模板里用的是Math.max不是直接赋值。理解了这一步整个算法就串起来了右指针负责开拓左指针负责收缩两指针都只朝一个方向移动整体时间复杂度 O(n)。2.3 滑动窗口的通用结构滑动窗口的代码模板其实只有四步刷多了你会发现很多题都是一个模子。第一步初始化左右指针和数据容器。第二步右指针移动把新字符加入容器。第三步内层 while/if 循环判断当前窗口是否满足约束不满足就收缩左指针。第四步更新答案。int left 0; for (int right 0; right n; right) { // 1. 加入 s[right] 到容器 // 2. 如果窗口不再满足约束移动 left // 3. 更新答案 }这道题和“长度最小的子数组”不同它没有内层 while 循环来反复收缩左指针。原因在于当left跳到lastIndex 1之后窗口一定合法不需要再继续收缩。如果用了 Set 并且通过 while 循环不断从窗口里删字符那就有内层循环。3. 无重复判断到底用什么数据结构这是这道题最容易被忽略的优化点。很多解法上来就HashSetCharacter能跑通但常数很大。实际面试里如果能说出不同方案的取舍会加分不少。3.1 方案对比这里我把常见的几种方案放在一张表里乍一看都能做但性能差距不小。题目说字符是 ASCII 码、数字、符号和空格也就是 ASCII 128 个字符。如果用更保险的做法扩展到 256 个扩展 ASCII 码也没问题。不使用额外的数据结构这个限制在力扣上其实是允许用数组当简易哈希表的。方案判断重复的依据典型代码时间复杂度空间复杂度备注HashSet集合中是否存在该字符set.contains(c)O(n) 均摊O(字符集)直观但常数大HashMap记录每个字符最后出现位置map.get(c)O(n) 均摊O(字符集)广为流传的解法int[128]数组下标即字符 ASCII 值last[c]O(n)O(1)最优解法推荐int[256]同上last[c]O(n)O(1)兼容扩展 ASCII注意我最后两行用的数组类型是int[]不是boolean[]。为什么因为我们要存“上一次出现的位置”而不是“是否出现过”。如果只存 boolean一旦发现重复你还得知道该把 left 移到哪没位置信息就得用 while 慢慢删。这里体现出一个好的数据结构设计能省多少事。3.2 数组下标为什么是 ASCII 值Java 的char本质是一个无符号 16 位整数范围是 0 到 65535。如果你直接开一个new int[128]把s.charAt(i)当成下标使用数组会自动完成字符到整数的转换。比如a对应 97A对应 65空格对应 32。数组默认值全是 0这会产生一个问题某个字符第一次出现的位置如果正好是 0会和“没出现过”混淆。所以初始化数组元素为 -1表示所有字符都没出现过这个细节特别重要后面代码里会看到。为什么上限用 128因为题目原说明里提到字符串由英文字母、数字、符号和空格组成覆盖 ASCII 范围完全够用。但为了稳健我会用 256不会多花多少空间。如果是中文场景比如给你一个包含 Unicode 的字符串ASCII 数组就不够了得用HashMapCharacter, Integer或者new int[128]改为 Map。面试时主动提一句这个边界会显得考虑问题更全面。3.3 为什么不推荐 while 循环收缩窗口用HashSet的经典思路是右指针不断把字符加进集合一旦遇到重复字符就不断移出s[left]同时left直到集合里没有再出现s[right]。这个过程用 while 循环最坏情况下 left 要移动 O(n) 次但均摊到整个流程依然是 O(n)。理论能过但实际操作里有几个别扭的地方。Set 里装的是当前窗口的字符集合如果窗口很长Set 的扩容和哈希计算有额外开销。而且 while 循环每次只删一个字符一旦重复字符在窗口的非常靠前位置left 要一步步挪过去不如直接用数组下标跳跃到lastIndex 1来得干净。所以我认为最优解不是 “Set while 收缩”而是 “数组 跳跃式左指针更新”。后者代码更短、常数更小、边界更容易想清楚。4. 从零到一写代码的完整过程很多教程直接甩出最优解读者看懂了但还是不会自己写。我这里从第一版开始一步一步演进。4.1 第一步用 HashMap 的思路跑通逻辑先不要追求性能极致用最容易理解的HashMap方案写一版。我见过很多初学者卡在这一步要么忘记了Math.max要么 key-value 存反了。这里放一个可以直接跑起来的版本。public int lengthOfLongestSubstring(String s) { int n s.length(); int ans 0; // key: 字符, value: 该字符上一次出现的位置 MapCharacter, Integer map new HashMap(); int left 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。举个例子s abba。当right2时遇到第二个b上一次出现位置是 1所以left跳到 2。接着right3时遇到第二个a上一次出现位置是 0如果直接赋值left会变成 1窗口退回去了。这不合法。所以必须Math.max(left, map.get(c)1)保证 left 只能右移不能左移。4.2 第二步把 HashMap 换成定长数组HashMa的实现虽然直观但涉及到装箱拆箱和哈希计算常数开销不小。既然题目限制字符集很小直接用数组模拟哈希表把“字符”映射成“数组下标”。public int lengthOfLongestSubstring(String s) { int n s.length(); int ans 0; // 记录每个字符上一次出现的位置初始化为 -1 int[] last new int[256]; Arrays.fill(last, -1); int left 0; for (int right 0; right n; right) { char c s.charAt(right); if (last[c] 0) { left Math.max(left, last[c] 1); } last[c] right; ans Math.max(ans, right - left 1); } return ans; }这一步的性能提升非常明显。力扣实测 HashMap 版本大概 5~7ms数组版本能压到 1~2ms。空间上数组无论有没有字符都占用固定 256 个 int也就是大约 1KB可以认为是 O(1) 空间。4.3 第三步极简版一行循环解决数组方案还能不能更短能。所有逻辑压在一个循环里代码不超过 15 行。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); left Math.max(left, last[c] 1); last[c] right; ans Math.max(ans, right - left 1); } return ans; }注意这版里if判断被合并进Math.max(left, last[c] 1)。当last[c] -1时last[c] 1 0此时max(left, 0)等于left不会产生副作用。所以if并不是必要的。这就是为什么初始化数组为 -1 很关键如果你初始化成 0那last[c]1一开始就是 1会导致 left 被误更新。4.4 四版代码对比复盘这里把四版方案放在一起对比方便你直观感受演进路线。暴力版可以跑但慢到离谱HashMap版是面试里最广为流传的版本适合讲思路数组版性能最优代码也不复杂极简版是手撕代码时最推荐的版本。版本时间复杂度空间复杂度优点缺点暴力版O(n³)O(min(n, 字符集))逻辑简单严重超时不可用滑动窗口HashMapO(n)O(字符集)易理解适用于任意字符集常数略大滑动窗口数组O(n)O(1)性能最优代码短仅适用于小字符集极简版O(n)O(1)面试手撕最快需理解 max 的巧妙性如果面试官问你“为什么空间复杂度是 O(1)”千万别说“因为只用了几个变量”。数组版本确实是 O(1)因为数组大小固定为 256不随输入长度变化。但 HashMap 版本严格说是 O(字符集大小)不过程序里字符集是有限的所以不少人也直接说 O(1)。5. 用 Go 再写一遍加深理解力扣支持多语言我建议至少用两门语言各写一遍因为不同语言对字符处理的细节不一样能暴露出你是否真的理解了算法本身。5.1 Go 版标准实现Go 的string底层是字节数组s[i]取到的是byte类型。如果字符串只包含 ASCII 字符直接对s[i]操作没问题。但如果包含中文、emoji 等 Unicode 字符s[i]只能取到 UTF-8 编码的一个字节会造成误判。这道题在力扣上的测试用例基本是 ASCII所以下面这个版本不会出错。如果面试时被追问如何支持 Unicode可以改用[]rune(s)转换成 rune 切片或是在遍历字符串时用for range它能自动按 rune 解码。func lengthOfLongestSubstring(s string) int { // last 数组记录每个字符上一次出现的下标 last : make([]int, 256) for i : range last { last[i] -1 } left, ans : 0, 0 for right : 0; right len(s); right { c : s[right] if last[c] 0 { if last[c]1 left { left last[c] 1 } } last[c] right if right-left1 ans { ans right - left 1 } } return ans }Go 的写法比 Java 更像手写过程。原因在于没有Math.max的流式写法得用 if 判断。这也迫使我们真正理解left的更新逻辑不是盲目取最大而是保证左指针最远只能到last[c]1。5.2 实测性能数据我用随机生成的长度 5 万的字符串测试过Go 版在线上的耗时基本在 0~1ms 之间内存消耗约 2.5MB。Java 数组版用 LeetCode 平台跑通常在 1~2ms内存约 40MB。HashMap 版本多在 5~7ms 徘徊。这里说的都是 leetcode 官方判题机的结果不同机器会有波动但相对差距比较稳定数组 HashMap 暴力版倍数关系很大。5.3 面试时被问“还能再优化吗”怎么答如果面试官继续追问可以从三方面回答。第一字符集裁剪。如果面试题明确说只包含小写字母就把数组从new int[256]缩成new int[26]或者用位运算压缩。节省的空间虽然不多但能体现你对题目条件的敏感度。第二避免Arrays.fill的开销。如果只在循环里给访问到的字符赋值不在一开始全置为 -1那需要额外用一个Integer或者boolean数组记录该字符是否被初始化过代码复杂度上升实际收益不大除非对极端性能有要求。第三针对较大字符集比如 Unicode 全量把数组换成HashMapCharacter, Integer是更合理的选择。这也正好回应了“为什么不用 Set”这个常见追问。Set 存的是当前窗口的字符集合HashMap 存的是每个字符上一次出现的位置两者能支持的操作不一样。Set 只能判断“存不存在”HashMap 能告诉你“在哪个位置”后者更适合跳跃式更新 left。6. 高频追问与变体题这道题在面试里出现的频率极高而且经常不是直接问原题而是稍加变形。我整理了几个典型的追问和变体。6.1 高频追问一为什么用 HashMap 而不用数组有些面试官会故意引导你先说数组方案然后问“如果字符串包含中文怎么办”。此时要回答数组下标本质是利用字符编码的数值做映射只适用于连续且范围小的字符集。Unicode 字符范围远大于 256直接开数组不现实用HashMap能把任意字符映射到它上次出现的位置。还有更细的追问方向为什么用int[]而不是boolean[]因为boolean只能表达“是否出现过”无法表达“出现在哪个位置”。缺失位置信息你遇到重复字符时没法知道 left 该收缩到哪儿只能回退到 while 循环里慢慢删。6.2 高频追问二能处理空字符串或 null 吗力扣原题给的范围是0 s.length所以s时直接返回 0。但如果面试官把边界改成String s nullJava 里s.length()会抛 NPE。稳妥的做法是在方法开头判断if (s null || s.length() 0) return 0;。虽然力扣不测 null但面试手写代码时主动加这个判断能避免被扣细节分。6.3 变体一最多包含两个不同字符的最长子串力扣上有原题 159思路类似只是窗口的合法性判断从“无重复字符”变成了“不同字符数 2”。此时用 HashMap 记录每个字符最后出现位置同时维护一个变量记录当前窗口内不同字符的数量。当窗口内不同字符数量超过 2 时把 left 移动到“最早一个不再出现的位置”之后。这个就比原题复杂一些因为你要知道每个字符最后出现位置中最小的那个才能确定删除谁的代价最小。最直接的方式是用有序结构比如TreeMapInteger, Integerkey 是位置value 是字符这样能快速找到最小位置。力扣上有个经典解法就是这么写的。不过实际生产里遇到这种需求更常用的是“双哈希表计数器”的滑动窗口理解起来更平滑。6.4 变体二至多包含 K 个不同字符的最长子串这就是上面题目的泛化。把“2 个不同字符”改成“K 个不同字符”模板几乎不变。关键在于维护不同字符的数量。我建议你练习顺序是原题 → 最大两个不同字符 → 最大 K 个不同字符你会发现滑动窗口的模板可以复用到很多场景。6.5 变体三字符串长度最长且字典序最小怎么处理这类变形在力扣上少见但面试官可能会口头问。如果要求多个最长子串里输出字典序最小的我的做法是先找到最长长度然后从所有长度为最长的子串里找字典序最小。如果用滑动窗口直接找可以记录当前最优子串的起点和终点遇到等长但字典序更小时更新。比较字典序用s.substring(start, end).compareTo(bestString)就行。7. 刷题过程中的心得与避坑指南7.1 三个最容易踩的坑第一个坑初始化数组为 0导致 left 被错误更新。前面提过数组默认值是 0而字符“第一次出现的位置”不需要是 0如果不把初始值设成 -1逻辑直接错。我刚开始刷的时候在这里栽过一次排查了好久。第二个坑忘了Math.max(left, ...)直接left last[c] 1。这个 bug 在字符串abba会暴露。left 一旦左移窗口就不再是当前 right 对应的合法窗口后续长度计算全错。这也是为什么很多人写出了“能过一部分用例但过不全”的代码。第三个坑ans初始化为 0 还是 1。当输入字符串为空ans0是正确答案当输入非空就算所有字符都重复最长不重复子串也至少为 1。只要循环里先更新 ans初始为 0 就安全。但如果你习惯先判断if (n 0) return 0;那可以把初始化为 1都能跑通关键是逻辑一致。7.2 我自己的排查技巧如果某次提交答案不对别急着看题解先手动模拟一遍小样例。比如abcabcbb跟着代码走一遍把 left 和 right 的每一步写下来很快能定位问题。还可以在循环里临时打印left、right、c、last[c]和ans肉眼核对每一轮窗口状态。这个方法对初学阶段特别有效刷了十几道滑动窗口之后你再把它删掉。一个非常实用的自测用例集合我每次重构代码都会跑一遍 - 0 - 1 abcabcbb - 3 bbbbb - 1 pwwkew - 3 abba - 2 au - 2 dvdf - 3 tmmzuxt - 5其中tmmzuxt是比较容易出错的用例。正确答案是 5对应子串是mzuxt。如果你用错误的方法在遇到第二个m时把 left 跳得太远或者忘了 Math.max就很容易算出 4。7.3 按什么顺序刷这道题的邻居题这道题在 hot100 里的编号是 4我之前整理过一份刷题顺序觉得对初学者比较友好推荐按这个链条走先做“两数之和”哈希表入门再做“无重复字符的最长子串”滑动窗口入门然后做“长度最小的子数组”滑动窗口前缀和接着做“最小覆盖子串”难题能检验滑动窗口掌握程度最后尝试“至多包含 K 个不同字符的最长子串”变体。这样从易到难每个题都在前一个题的基础上增加一个复杂度维度。另外多说一句力扣的“hot100”之所以叫 hot100因为它覆盖了面试最高频的题目模式。与其盲目刷 500 题不如把 hot100 吃透。尤其滑动窗口这一块掌握这一题的核心逻辑等于掌握了一类题的钥匙。