第一次刷 LeetCode 的同学往往在第三题就卡住了。前面两题还停留在“暴力能不能过”的挣扎里突然冒出来一个“无重复字符的最长子串”嘴上念着“这不是用 substring 挨个检查吗”心里已经开始发怵。这道题之所以是经典的不能再经典的面试题并不是因为它本身有多难而是它在考察一个极其重要的基础能力滑动窗口。可以说搞懂这道题你就等于拿到了一大类字符串和数组子区间问题的钥匙。题目本身一句话给定一个字符串请你找出其中不含有重复字符的最长子串的长度。你用暴力循环也能解出来但真正要命的不是“能不能解出来”而是“能不能在线性时间内解出来”。这篇文章我会从暴力思路开始一步步把它推到最优解把 Hash 表、双指针、窗口收缩这些核心细节都拆开揉碎讲清楚最后再用真实的用例把这套方法走一遍。适合的人群很明确刚开始刷题的 LeetCode 新手准备面试想系统整理滑动窗口的同学以及面试完想回头总结一下的拖延症患者。1. 从暴力解到滑动窗口为什么双指针能行1.1 先把题意拆干净什么是“无重复字符的最长子串”很多人在第一步就犯了错误他们把“子串”和“子序列”搞混了。子串要求在原字符串中必须是连续的也就是说你不能跳着挑字符只能沿着索引顺序连续截取。而子序列是可以跳着选的。题目说的是“最长子串”所以我们要找的是一段连续区间。举个例子字符串abcabcbb它的无重复字符最长子串是abc长度是 3。很多初学者会问abca也算连续但是里面有重复的a不算。abcab更长但还是有重复。所以这个题的本质是在所有连续区间中找一个区间这个区间内的所有字符两两不重复并且区间的长度最大。我在实际讲这道题的时候最喜欢用一个生活化类比想象你在逛一条由字符组成的街每个字符是一家商店。你要找到一条最长的连续的街段每一家商店都各不相同没有重复店铺。如果前面出现了一个你见过的店铺你就要从这家店的下一个位置重新开始看。这就是滑动窗口的核心。1.2 暴力法为什么不行三重循环的致命伤最直接的办法是枚举所有子串。字符串长度为 n子串的数量是 O(n²) 个每个子串要检查是否无重复检查的过程又是 O(n)。所以总的时间复杂度是 O(n³)。对于 LeetCode 的测试用例字符串通常能到几万的长度O(n³) 直接爆炸。可以优化一步在枚举子串的过程中边遍历边判断重复不需要每次都重新扫描整个区间。这能把 O(n³) 降到 O(n²)。比如枚举左端点 i然后右端点 j 从 i 开始不断扩张用一个 HashSet 记录当前区间里的字符。每遇到一个新字符先看它在不在集合里不在就加进去然后更新答案长度如果在就说明以 i 开头的区间到头了直接进入下一个 i。这个 O(n²) 的解法确实能过一部分测试但面对极端数据仍然超时。我在给学员讲的时候经常让他们先把这种解法写出来——不是为了提交而是为了体会一件事右端点 j 在不断前进的时候左端点 i 每移动一格就要重新构造整个 HashSet这里面有大量的重复计算。滑动窗口的思路就是从这里诞生的我们能不能不让左端点一格一格地“重新开始”而是让整个区间像一个窗口那样右端前进左端收缩窗口整体滑过去。1.3 窗口思想的诞生两个指针如何做到线性扫描这里的核心改变在于不要每轮都从左端点重新构建窗口。我们用两个指针 left 和 right初始都指向 0。right 一步一步往右扩张探索新的字符left 只在必要的时候向右移动收缩窗口。窗口内的这段区间始终保持“无重复字符”这个约束条件。为什么这样能做到线性因为 right 最多从 0 走到 n-1left 最多也从 0 走到 n-1两个指针加起来移动了不超过 2n 步。每一个字符最多被 left 访问一次、被 right 访问一次所以总时间是 O(n)。这就是滑动窗口把 O(n²) 降成 O(n) 的关键所在——每个指针移动的总次数是有上限的。但这里有一个细节必须理解透彻窗口收缩的时候left 怎么走最简单直观的做法是当 right 发现当前字符重复了就让 left 一格一格往右挪每挪一格就从集合里删掉一个字符直到把窗口里那个和当前字符重复的字符删掉为止。这个过程看起来是 while 循环但所有 left 的移动加起来最多 n 次所以均摊下来依旧是 O(n)。这里不复杂但是很多人一写代码就把顺序搞反了后面我会专门讲到。2. 三种经典写法逐级拆解从 HashSet 到数组优化2.1 写法一HashSet 配合双指针最稳妥的入门版这个版本最适合新手写逻辑最直接也不容易出错。核心思路是窗口内的所有字符都存在一个HashSetCharacter里面。right 每次滑到新位置先检查当前字符 c 是否已经存在于 set 中。如果不存在就加入 set更新最大长度right 继续右移如果存在就说明出现了重复此时需要移动 left把s.charAt(left)从 set 里移除然后 left直到窗口里不再包含这个重复字符为止。这里有一个新手特别容易犯的错误重复字符是 s.charAt(right)当你把窗口里的左边字符一个一个移除的时候很可能你移除的并不是那个重复字符本身而是它前面的无关字符。但这没关系因为我们的目标是“把窗口里那个重复字符移除掉”所以在 while 循环里只要s.charAt(left)不等于s.charAt(right)就一路 remove 一路 left一旦找到了那个重复字符把它移除后left 再走一步窗口就正好排除了这个重复字符然后可以把 s.charAt(right) 加入 set。我每次都建议初学者把这个 while 循环写完整先用 left 走到正确的位置再执行加入操作。伪代码如下public int lengthOfLongestSubstring(String s) { SetCharacter set new HashSet(); int left 0, maxLen 0; for (int right 0; right s.length(); right) { char c s.charAt(right); while (set.contains(c)) { set.remove(s.charAt(left)); left; } set.add(c); maxLen Math.max(maxLen, right - left 1); } return maxLen; }这段代码跑在abcabcbb上过程很值得亲手画一遍。窗口先是abcright 滑到第二个a时发现 set 里有a于是 left 开始移动依次移除a、b、cleft 最终停在第二个a的位置上窗口变成a然后加入新的a窗口变成abca吗不对因为刚才 left 已经把旧窗口里的abc全部移除了此时把新的 c a加入 set窗口是a长度 1。实际上这个过程因为循环的先后顺序你会发现窗口从abc变成bca再变成cab。总之理解是最大长度被记录下来了。2.2 写法二HashMap 记录下标left 直接跳转的进阶版HashSet 的版本虽然正确但是有个小问题left 是一格一格挪的某些场景下这个 while 循环会执行很多次。比如字符串是abcaright 走到第二个a时left 需要从 0 一路移到 1 才能把重复的a移除掉。如果字符串特别长且重复字符离 left 很远那这个 while 循环就要跑很多次。虽然均摊时间复杂度依旧是 O(n)但我们有更聪明的做法用HashMap记录每个字符最近一次出现的下标这样 left 可以直接跳到合适的位置一步到位。这个版本的核心逻辑是遍历字符串对于每个字符 c如果 c 已经出现过并且上一次出现的位置prevIndex在窗口内即prevIndex left那么直接令left prevIndex 1把左边界跳转到重复字符的下一个位置。然后更新map.put(c, right)记录这个字符最新的下标。这里最容易被忽略的一个细节是为什么跳转条件必须是prevIndex left而不是只要存在就跳转因为字符上一次出现的位置可能已经在窗口之外了比如 left 早就右移过了那个位置此时这个旧位置对当前窗口没有影响不能用来收缩窗口。如果不加这个条件left 就可能会回退导致窗口长度计算错误。public int lengthOfLongestSubstring(String s) { MapCharacter, Integer map new HashMap(); int left 0, maxLen 0; for (int right 0; right s.length(); right) { char c s.charAt(right); if (map.containsKey(c)) { int prev map.get(c); if (prev left) { left prev 1; } } map.put(c, right); maxLen Math.max(maxLen, right - left 1); } return maxLen; }注意一个细节如果prev left说明该字符上一次出现的位置不需要处理但 map.put 仍然会更新为当前位置。这种写法下最长长度可能出现在窗口的任意位置不会出现回退问题。2.3 写法三用数组当哈希表极致性能的关键HashMap 本身性能已经不错但每次 get、put 涉及装箱拆箱和哈希计算常数开销不小。在面试中如果你能直接写出更优的版本面试官通常会更认可。对于由 ASCII 字符组成的字符串我们可以用一个大小为 128 的 int 数组来代替 HashMap数组的索引是字符的 ASCII 码数组的值是“该字符最近一次出现的位置 1”。为什么要存“位置 1”因为你最终想要的是left prevIndex 1。如果直接存 prevIndex那么每次判断后还要加 1如果存的是“位置 1”那就可以直接令left Math.max(left, lastIndex[c])。另外数组初始化值全部为 0而字符串下标从 0 开始所以用 0 表示“还没有出现过”是安全的。这可以说是一个很自然的哨兵设计。public int lengthOfLongestSubstring(String s) { int[] last new int[128]; int left 0, maxLen 0; for (int right 0; right s.length(); right) { char c s.charAt(right); // last[c] 存的是上次出现位置 1默认 0 表示未出现 if (last[c] left) { left last[c]; } last[c] right 1; maxLen Math.max(maxLen, right - left 1); } return maxLen; }这个版本的时间复杂度仍然是 O(n)因为数组的访问是 O(1) 且没有哈希计算空间复杂度是 O(字符集大小)这里就是 128是一个常数。如果你的输入可能包含扩展 ASCII 或更广泛的字符集数组大小可以根据需要调整。但如果字符串可能包含中文字符、emoji 等建议回退到 HashMap 或者扩展数组到 Unicode 范围。三种写法对比下来我个人的建议是面试时先用 HashSet 版本讲通思路然后“顺手”优化到 HashMap 版本最后如果面试官追问性能再亮出数组版本。这样既展示了你会从暴力思维进化到滑动窗口也展示了你有性能意识。3. 实操过程与边界讨论用完整用例走一遍代码3.1 典型用例逐步演示abcabcbb的完整窗口变化这道题最经典的用例就是abcabcbb。我把整个运行过程完整列出来帮助你把窗口的移动可视化。初始left 0right 0窗口空。right 指向a窗口无a加入窗口a长度 1。right 指向b窗口无b加入窗口ab长度 2。right 指向c窗口无c加入窗口abc长度 3。right 指向a窗口中已有a。用 HashSet 版本left 出发移除 left 指向的aleft 变成 1窗口变成bc再加入右边这个a窗口变成bca。长度仍为 3。right 指向b窗口中已有b。left 从 1 开始移除bleft 变成 2窗口ca再加入新b窗口cab长度 3。right 指向c窗口中已有c。left 从 2 开始移除cleft 变成 3窗口ab再加入新c窗口abc长度 3。right 指向b窗口中已有b。left 从 3 开始移除aleft 变成 4窗口bc再移除bleft 变成 5窗口c再加入新b窗口cb长度 2。此时继续更新 maxLen仍然是 3。right 指向b窗口中已有b。这次操作较多left 从 5 一路移除c、b最终窗口只有新加的b长度 1。最终结果 maxLen 3。这个例子完美地展示了窗口的扩张和收缩过程。如果你在本地 Debug建议打印每次循环的 left、right、窗口内容你对“为什么最长长度是 3”会有非常直观的感受。3.2 特殊边界条件空串、单字符、全重复字符串光会跑经典用例不够面试官十个里有八个会问边界条件。第一种是空字符串。三种写法在这个输入下的结果都是 0因为循环直接不进maxLen 为 0。第二种是单字符a循环执行一次窗口长度 1结果为 1。这个逻辑很顺但很多人写的时候会把初始 maxLen 设成 0然后忘记更新导致返回初始值。代码里的Math.max(maxLen, right - left 1)这种写法就规避了这个问题。第三种是全部字符都一样比如aaaa。这里就特别能体现两种收缩方式的不同了。HashSet 版本每次 right 遇到下一个a时left 都会一格一格移动直到把窗口里的那个a移除然后新的a再加入。每轮窗口长度都只有 1最大长度就是 1。这个场景下 HashSet 版本的循环执行次数比较多但均摊还是 O(n)。HashMap 版本中第一个a记录下标 0第二个a时 prevIndex0 left0left 直接跳到 1第三个a时 prevIndex1left1left 跳到 2以此类推。每次都是 O(1) 跳转一气呵成。第四种边界是字符串包含空格、标点等可见 ASCII 字符。比如ab b这种东西。如果用了数组大小为 128 的写法空格字符的 ASCII 是 32也在范围内不影响正确性。但如果字符串中有换行符之类的控制字符ASCII 码也在 128 以内同样安全。只有在处理中文或多字节字符的时候char 的取值可能超过 128这时就不能直接用int[128]了需要用int[65536]或者直接用 HashMap。3.3 一个隐蔽的 bugprevIndex left时到底要不要更新左边界这次我特意写一个容易出错的场景。假设字符串是abba。用 HashMap 版本的逻辑来走一遍right0a加入left0maxLen1。right1b加入left0maxLen2。right2字符是bprevIndex1prevleftleft 跳转到 2。right3字符是aprevIndex0此时prevIndex0 小于 left2。如果我们不加prev left这个判断而是看见 containsKey 就更新 leftprev11那么 left 就从 2 回退成了 1窗口被错误地扩大了最终 maxLen 会算成 3但正确答案显然是 2。所以这个prev left的判断不是可有可无的它是防止 left 回退的保险栓。在一些版本的题解里写法是left Math.max(left, prev 1)本质上也一样用 max 保证 left 只能向右不能向左。这个细节如果你能在面试中主动说出来基本上就等于告诉面试官你是真的理解滑动窗口而不是背代码。4. 复杂度、应用场景与面试扩展这道题能带给你什么4.1 时间与空间复杂度为什么说均摊 O(n)滑动窗口的复杂度分析其实是个很容易被小看的点。先说时间复杂度。right 指针从 0 到 n-1 一共遍历 n 次这是外循环毫无疑问 O(n)。left 指针在 HashSet 版本里可能会在某个循环中移动多次但是 left 总共只会向右移动不会向左回退所以它最多也只能移动 n 次。所以即使内层有个 while 循环总的移动次数限制在 2n 以内均摊到每个循环里就是 O(1)。所以总的时间复杂度是 O(n)。空间复杂度方面HashSet 和 HashMap 版本需要存储字符和下标最坏情况下窗口可能包含所有不同的字符所以空间是 O(min(n, m))其中 m 是字符集大小。如果令字符集大小固定比如 ASCII 是 128则空间复杂度是 O(1)。数组版本就特别直白固定大小的数组空间就是 O(1)。很多文章把这个讲得很玄乎说“每个字符最多被访问两次”其实就是 left 和 right 各访问一次的总和。理解了这个你后面再去写“至多包含 K 个不同字符的最长子串”“最小覆盖子串”这些问题时就会自然地把同一个框架套过去。4.2 真实场景中的应用滑动窗口不只在面试里出现不要觉得滑动窗口只是算法题库里的怪物它在真实业务里比你想的更常见。比如数据分析中我们要找出一个时间窗口内连续不重复的事件标识符。再比如日志解析系统里要判断一段时间窗口内有没有重复请求 ID本质就是无重复子串的变体。文本处理中的最长无重复子串可以直接用于序列去重、长度限制校验。最典型的实际工程例子是 TCP 协议里的滑动窗口但那属于网络层的概念和这道题的实现不完全一致。更贴近的例子是某些限流系统中的“滑动时间窗口”它维护一个时间窗口的请求记录新请求到达时移除过期记录逻辑上和这道题“右指针扩张、左指针收缩”如出一辙。所以刷这道题的时候不要只用它来应付面试要把窗口的思维内化成一种处理流式数据的习惯。4.3 面试中的变体和拔高从无重复到至多 K 个不同字符这道题的变体非常多面试官很喜欢在这条线上逐步加码。最常见的是 LeetCode 340 题“至多包含 K 个不同字符的最长子串”。这道题和原题的区别在于窗口内的约束条件从“无重复字符”变成了“不同字符数量 ≤ K”。实现上把 HashSet 换成 HashMap删除的时候要去移除一个字符的计数当计数降到 0 时才真正删除。这个变体考验的是你对“窗口内的状态维护”是否真正理解而不只是背公式。另一个变体是“字符串的排列”LeetCode 567它要求判断 s2 是否包含 s1 的某个排列这需要固定长度的窗口同时维护字符频率表。当你熟练掌握了无重复字符这道题的双指针收缩逻辑写这类变体时你会发现骨架没变变的只是窗口的约束条件和状态记录的方式。第 4 章我再加一条实战建议面试时拿到这道题不要上来就写最优解。先讲一遍暴力解法作为切入点明它的痛点然后过渡到滑动窗口。如果面试官问你“还有没有更好的优化”再亮出 HashMap 跳转和数组版本。这一套下来的展示效果远比直接“秒写”最优解要好得多因为你展示的是完整的思维链而不是单薄的最优解。最后分享一个我在刷题 debug 阶段经常用的小技巧单独建一个测试类把字符串改成pwwkew然后在循环里打印left、right、当前窗口字符集合。你会发现当窗口收缩时字符并不是一次性全部清空的而是一个个被弹出去。这个过程看懂了你就彻底掌握了滑动窗口的精髓。这道题我一直认为是 LeetCode 前一百题里最值得反复写的一题因为它的思想可以顺滑地迁移到后面几十道双指针和字符串题上多花点时间在上面绝对不亏。 第一次刷 LeetCode 的同学往往在第三题就卡住了。前面两题还停留在“暴力能不能过”的挣扎里突然冒出来一个“无重复字符的最长子串”嘴上念着“这不是用 substring 挨个检查吗”心里已经开始发怵。这道题之所以是经典的不能再经典的面试题并不是因为它本身有多难而是它在考察一个极其重要的基础能力滑动窗口。可以说搞懂这道题你就等于拿到了一大类字符串和数组子区间问题的钥匙。题目本身一句话给定一个字符串请你找出其中不含有重复字符的最长子串的长度。你用暴力循环也能解出来但真正要命的不是“能不能解出来”而是“能不能在线性时间内解出来”。这篇文章我会从暴力思路开始一步步把它推到最优解把 Hash 表、双指针、窗口收缩这些核心细节都拆开揉碎讲清楚最后再用真实的用例把这套方法走一遍。适合的人群很明确刚开始刷题的 LeetCode 新手准备面试想系统整理滑动窗口的同学以及面试完想回头总结一下的拖延症患者。1. 从暴力解到滑动窗口为什么双指针能行1.1 先把题意拆干净什么是“无重复字符的最长子串”很多人在第一步就犯了错误他们把“子串”和“子序列”搞混了。子串要求在原字符串中必须是连续的也就是说你不能跳着挑字符只能沿着索引顺序连续截取。而子序列是可以跳着选的。题目说的是“最长子串”所以我们要找的是一段连续区间。举个例子字符串abcabcbb它的无重复字符最长子串是abc长度是 3。很多初学者会问abca也算连续但是里面有重复的a不算。abcab更长但还是有重复。所以这个题的本质是在所有连续区间中找一个区间这个区间内的所有字符两两不重复并且区间的长度最大。我在实际讲这道题的时候最喜欢用一个生活化类比想象你在逛一条由字符组成的街每个字符是一家商店。你要找到一条最长的连续的街段每一家商店都各不相同没有重复店铺。如果前面出现了一个你见过的店铺你就要从这家店的下一个位置重新开始看。这就是滑动窗口的核心。1.2 暴力法为什么不行三重循环的致命伤最直接的办法是枚举所有子串。字符串长度为 n子串的数量是 O(n²) 个每个子串要检查是否无重复检查的过程又是 O(n)。所以总的时间复杂度是 O(n³)。对于 LeetCode 的测试用例字符串通常能到几万的长度O(n³) 直接爆炸。可以优化一步在枚举子串的过程中边遍历边判断重复不需要每次都重新扫描整个区间。这能把 O(n³) 降到 O(n²)。比如枚举左端点 i然后右端点 j 从 i 开始不断扩张用一个 HashSet 记录当前区间里的字符。每遇到一个新字符先看它在不在集合里不在就加进去然后更新答案长度如果在就说明以 i 开头的区间到头了直接进入下一个 i。这个 O(n²) 的解法确实能过一部分测试但面对极端数据仍然超时。我在给学员讲的时候经常让他们先把这种解法写出来——不是为了提交而是为了体会一件事右端点 j 在不断前进的时候左端点 i 每移动一格就要重新构造整个 HashSet这里面有大量的重复计算。滑动窗口的思路就是从这里诞生的我们能不能不让左端点一格一格地“重新开始”而是让整个区间像一个窗口那样右端前进左端收缩窗口整体滑过去。1.3 窗口思想的诞生两个指针如何做到线性扫描这里的核心改变在于不要每轮都从左端点重新构建窗口。我们用两个指针 left 和 right初始都指向 0。right 一步一步往右扩张探索新的字符left 只在必要的时候向右移动收缩窗口。窗口内的这段区间始终保持“无重复字符”这个约束条件。为什么这样能做到线性因为 right 最多从 0 走到 n-1left 最多也从 0 走到 n-1两个指针加起来移动了不超过 2n 步。每一个字符最多被 left 访问一次、被 right 访问一次所以总时间是 O(n)。这就是滑动窗口把 O(n²) 降成 O(n) 的关键所在——每个指针移动的总次数是有上限的。但这里有一个细节必须理解透彻窗口收缩的时候left 怎么走最简单直观的做法是当 right 发现当前字符重复了就让 left 一格一格往右挪每挪一格就从集合里删掉一个字符直到把窗口里那个和当前字符重复的字符删掉为止。这个过程看起来是 while 循环但所有 left 的移动加起来最多 n 次所以均摊下来依旧是 O(n)。这里不复杂但是很多人一写代码就把顺序搞反了后面我会专门讲到。2. 三种经典写法逐级拆解从 HashSet 到数组优化2.1 写法一HashSet 配合双指针最稳妥的入门版这个版本最适合新手写逻辑最直接也不容易出错。核心思路是窗口内的所有字符都存在一个HashSetCharacter里面。right 每次滑到新位置先检查当前字符 c 是否已经存在于 set 中。如果不存在就加入 set更新最大长度right 继续右移如果存在就说明出现了重复此时需要移动 left把s.charAt(left)从 set 里移除然后 left直到窗口里不再包含这个重复字符为止。这里有一个新手特别容易犯的错误重复字符是 s.charAt(right)当你把窗口里的左边字符一个一个移除的时候很可能你移除的并不是那个重复字符本身而是它前面的无关字符。但这没关系因为我们的目标是“把窗口里那个重复字符移除掉”所以在 while 循环里只要s.charAt(left)不等于s.charAt(right)就一路 remove 一路 left一旦找到了那个重复字符把它移除后left 再走一步窗口就正好排除了这个重复字符然后可以把 s.charAt(right) 加入 set。我每次都建议初学者把这个 while 循环写完整先用 left 走到正确的位置再执行加入操作。伪代码如下public int lengthOfLongestSubstring(String s) { SetCharacter set new HashSet(); int left 0, maxLen 0; for (int right 0; right s.length(); right) { char c s.charAt(right); while (set.contains(c)) { set.remove(s.charAt(left)); left; } set.add(c); maxLen Math.max(maxLen, right - left 1); } return maxLen; }这段代码跑在abcabcbb上过程很值得亲手画一遍。窗口先是abcright 滑到第二个a时发现 set 里有a于是 left 开始移动依次移除a、b、cleft 最终停在第二个a的位置上窗口变成a然后加入新的a窗口变成abca吗不对因为刚才 left 已经把旧窗口里的abc全部移除了此时把新的 c a加入 set窗口是a长度 1。实际上这个过程因为循环的先后顺序你会发现窗口从abc变成bca再变成cab。总之理解是最大长度被记录下来了。2.2 写法二HashMap 记录下标left 直接跳转的进阶版HashSet 的版本虽然正确但是有个小问题left 是一格一格挪的某些场景下这个 while 循环会执行很多次。比如字符串是abcaright 走到第二个a时left 需要从 0 一路移到 1 才能把重复的a移除掉。如果字符串特别长且重复字符离 left 很远那这个 while 循环就要跑很多次。虽然均摊时间复杂度依旧是 O(n)但我们有更聪明的做法用HashMap记录每个字符最近一次出现的下标这样 left 可以直接跳到合适的位置一步到位。这个版本的核心逻辑是遍历字符串对于每个字符 c如果 c 已经出现过并且上一次出现的位置prevIndex在窗口内即prevIndex left那么直接令left prevIndex 1把左边界跳转到重复字符的下一个位置。然后更新map.put(c, right)记录这个字符最新的下标。这里最容易被忽略的一个细节是为什么跳转条件必须是prevIndex left而不是只要存在就跳转因为字符上一次出现的位置可能已经在窗口之外了比如 left 早就右移过了那个位置此时这个旧位置对当前窗口没有影响不能用来收缩窗口。如果不加这个条件left 就可能会回退导致窗口长度计算错误。public int lengthOfLongestSubstring(String s) { MapCharacter, Integer map new HashMap(); int left 0, maxLen 0; for (int right 0; right s.length(); right) { char c s.charAt(right); if (map.containsKey(c)) { int prev map.get(c); if (prev left) { left prev 1; } } map.put(c, right); maxLen Math.max(maxLen, right - left 1); } return maxLen; }注意一个细节如果prev left说明该字符上一次出现的位置不需要处理但 map.put 仍然会更新为当前位置。这种写法下最长长度可能出现在窗口的任意位置不会出现回退问题。2.3 写法三用数组当哈希表极致性能的关键HashMap 本身性能已经不错但每次 get、put 涉及装箱拆箱和哈希计算常数开销不小。在面试中如果你能直接写出更优的版本面试官通常会更认可。对于由 ASCII 字符组成的字符串我们可以用一个大小为 128 的 int 数组来代替 HashMap数组的索引是字符的 ASCII 码数组的值是“该字符最近一次出现的位置 1”。为什么要存“位置 1”因为你最终想要的是left prevIndex 1。如果直接存 prevIndex那么每次判断后还要加 1如果存的是“位置 1”那就可以直接令left Math.max(left, lastIndex[c])。另外数组初始化值全部为 0而字符串下标从 0 开始所以用 0 表示“还没有出现过”是安全的。这可以说是一个很自然的哨兵设计。public int lengthOfLongestSubstring(String s) { int[] last new int[128]; int left 0, maxLen 0; for (int right 0; right s.length(); right) { char c s.charAt(right); // last[c] 存的是上次出现位置 1默认 0 表示未出现 if (last[c] left) { left last[c]; } last[c] right 1; maxLen Math.max(maxLen, right - left 1); } return maxLen; }这个版本的时间复杂度仍然是 O(n)因为数组的访问是 O(1) 且没有哈希计算空间复杂度是 O(字符集大小)这里就是 128是一个常数。如果你的输入可能包含扩展 ASCII 或更广泛的字符集数组大小可以根据需要调整。但如果字符串可能包含中文字符、emoji 等建议回退到 HashMap 或者扩展数组到 Unicode 范围。三种写法对比下来我个人的建议是面试时先用 HashSet 版本讲通思路然后“顺手”优化到 HashMap 版本最后如果面试官追问性能再亮出数组版本。这样既展示了你会从暴力思维进化到滑动窗口也展示了你有性能意识。3. 实操过程与边界讨论用完整用例走一遍代码3.1 典型用例逐步演示abcabcbb的完整窗口变化这道题最经典的用例就是abcabcbb。我把整个运行过程完整列出来帮助你把窗口的移动可视化。初始left 0right 0窗口空。right 指向a窗口无a加入窗口a长度 1。right 指向b窗口无b加入窗口ab长度 2。right 指向c窗口无c加入窗口abc长度 3。right 指向a窗口中已有a。用 HashSet 版本left 出发移除 left 指向的aleft 变成 1窗口变成bc再加入右边这个a窗口变成bca。长度仍为 3。right 指向b窗口中已有b。left 从 1 开始移除bleft 变成 2窗口ca再加入新b窗口cab长度 3。right 指向c窗口中已有c。left 从 2 开始移除cleft 变成 3窗口ab再加入新c窗口abc长度 3。right 指向b窗口中已有b。left 从 3 开始移除aleft 变成 4窗口bc再移除bleft 变成 5窗口c再加入新b窗口cb长度 2。此时继续更新 maxLen仍然是 3。right 指向b窗口中已有b。这次操作较多left 从 5 一路移除c、b最终窗口只有新加的b长度 1。最终结果 maxLen 3。这个例子完美地展示了窗口的扩张和收缩过程。如果你在本地 Debug建议打印每次循环的 left、right、窗口内容你对“为什么最长长度是 3”会有非常直观的感受。3.2 特殊边界条件空串、单字符、全重复字符串光会跑经典用例不够面试官十个里有八个会问边界条件。第一种是空字符串。三种写法在这个输入下的结果都是 0因为循环直接不进maxLen 为 0。第二种是单字符a循环执行一次窗口长度 1结果为 1。这个逻辑很顺但很多人写的时候会把初始 maxLen 设成 0然后忘记更新导致返回初始值。代码里的Math.max(maxLen, right - left 1)这种写法就规避了这个问题。第三种是全部字符都一样比如aaaa。这里就特别能体现两种收缩方式的不同了。HashSet 版本每次 right 遇到下一个a时left 都会一格一格移动直到把窗口里的那个a移除然后新的a再加入。每轮窗口长度都只有 1最大长度就是 1。这个场景下 HashSet 版本的循环执行次数比较多但均摊还是 O(n)。HashMap 版本中第一个a记录下标 0第二个a时 prevIndex0 left0left 直接跳到 1第三个a时 prevIndex1left1left 跳到 2以此类推。每次都是 O(1) 跳转一气呵成。第四种边界是字符串包含空格、标点等可见 ASCII 字符。比如ab b这种东西。如果用了数组大小为 128 的写法空格字符的 ASCII 是 32也在范围内不影响正确性。但如果字符串中有换行符之类的控制字符ASCII 码也在 128 以内同样安全。只有在处理中文或多字节字符的时候char 的取值可能超过 128这时就不能直接用int[128]了需要用int[65536]或者直接用 HashMap。3.3 一个隐蔽的 bugprevIndex left时到底要不要更新左边界这次我特意写一个容易出错的场景。假设字符串是abba。用 HashMap 版本的逻辑来走一遍right0a加入left0maxLen1。right1b加入left0maxLen2。right2字符是bprevIndex1prevleftleft 跳转到 2。right3字符是aprevIndex0此时prevIndex0 小于 left2。如果我们不加prev left这个判断而是看见 containsKey 就更新 leftprev11那么 left 就从 2 回退成了 1窗口被错误地扩大了最终 maxLen 会算成 3但正确答案显然是 2。所以这个prev left的判断不是可有可无的它是防止 left 回退的保险栓。在一些版本的题解里写法是left Math.max(left, prev 1)本质上也一样用 max 保证 left 只能向右不能向左。这个细节如果你能在面试中主动说出来基本上就等于告诉面试官你是真的理解滑动窗口而不是背代码。4. 复杂度、应用场景与面试扩展这道题能带给你什么4.1 时间与空间复杂度为什么说均摊 O(n)滑动窗口的复杂度分析其实是个很容易被小看的点。先说时间复杂度。right 指针从 0 到 n-1 一共遍历 n 次这是外循环毫无疑问 O(n)。left 指针在 HashSet 版本里可能会在某个循环中移动多次但是 left 总共只会向右移动不会向左回退所以它最多也只能移动 n 次。所以即使内层有个 while 循环总的移动次数限制在 2n 以内均摊到每个循环里就是 O(1)。所以总的时间复杂度是 O(n)。空间复杂度方面HashSet 和 HashMap 版本需要存储字符和下标最坏情况下窗口可能包含所有不同的字符所以空间是 O(min(n, m))其中 m 是字符集大小。如果令字符集大小固定比如 ASCII 是 128则空间复杂度是 O(1)。数组版本就特别直白固定大小的数组空间就是 O(1)。很多文章把这个讲得很玄乎说“每个字符最多被访问两次”其实就是 left 和 right 各访问一次的总和。理解了这个你后面再去写“至多包含 K 个不同字符的最长子串”“最小覆盖子串”这些问题时就会自然地把同一个框架套过去。4.2 真实场景中的应用滑动窗口不只在面试里出现不要觉得滑动窗口只是算法题库里的怪物它在真实业务里比你想的更常见。比如数据分析中我们要找出一个时间窗口内连续不重复的事件标识符。再比如日志解析系统里要判断一段时间窗口内有没有重复请求 ID本质就是无重复子串的变体。文本处理中的最长无重复子串可以直接用于序列去重、长度限制校验。最典型的实际工程例子是 TCP 协议里的滑动窗口但那属于网络层的概念和这道题的实现不完全一致。更贴近的例子是某些限流系统中的“滑动时间窗口”它维护一个时间窗口的请求记录新请求到达时移除过期记录逻辑上和这道题“右指针扩张、左指针收缩”如出一辙。所以刷这道题的时候不要只用它来应付面试要把窗口的思维内化成一种处理流式数据的习惯。4.3 面试中的变体和拔高从无重复到至多 K 个不同字符这道题的变体非常多面试官很喜欢在这条线上逐步加码。最常见的是 LeetCode 340 题“至多包含 K 个不同字符的最长子串”。这道题和原题的区别在于窗口内的约束条件从“无重复字符”变成了“不同字符数量 ≤ K”。实现上把 HashSet 换成 HashMap删除的时候要去移除一个字符的计数当计数降到 0 时才真正删除。这个变体考验的是你对“窗口内的状态维护”是否真正理解而不只是背公式。另一个变体是“字符串的排列”LeetCode 567它要求判断 s2 是否包含 s1 的某个排列这需要固定长度的窗口同时维护字符频率表。当你熟练掌握了无重复字符这道题的双指针收缩逻辑写这类变体时你会发现骨架没变变的只是窗口的约束条件和状态记录的方式。第 4 章我再加一条实战建议面试时拿到这道题不要上来就写最优解。先讲一遍暴力解法作为切入点明它的痛点然后过渡到滑动窗口。如果面试官问你“还有没有更好的优化”再亮出 HashMap 跳转和数组版本。这一套下来的展示效果远比直接“秒写”最优解要好得多因为你展示的是完整的思维链而不是单薄的最优解。最后分享一个我在刷题 debug 阶段经常用的小技巧单独建一个测试类把字符串改成pwwkew然后在循环里打印left、right、当前窗口字符集合。你会发现当窗口收缩时字符并不是一次性全部清空的而是一个个被弹出去。这个过程看懂了你就彻底掌握了滑动窗口的精髓。这道题我一直认为是 LeetCode 前一百题里最值得反复写的一题因为它的思想可以顺滑地迁移到后面几十道双指针和字符串题上多花点时间在上面绝对不亏。