第一次刷 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-1，left 最多也从 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 配合双指针，最稳妥的入门版
这个版本最适合新手写，逻辑最直接，也不容易出错。核心思路是：窗口内的所有字符都存在一个HashSet<Character>里面。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) { Set<Character> 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"上，过程很值得亲手画一遍。窗口先是"abc"，right 滑到第二个a时，发现 set 里有a，于是 left 开始移动，依次移除a、b、c，left 最终停在第二个a的位置上，窗口变成"a"，然后加入新的a，窗口变成"abca"吗？不对，因为刚才 left 已经把旧窗口里的abc全部移除了，此时把新的 c =a加入 set，窗口是"a"，长度 1。实际上这个过程因为循环的先后顺序，你会发现窗口从"abc"变成"bca"再变成"cab"。总之理解是最大长度被记录下来了。
2.2 写法二：HashMap 记录下标，left 直接跳转的进阶版
HashSet 的版本虽然正确，但是有个小问题：left 是一格一格挪的，某些场景下这个 while 循环会执行很多次。比如字符串是"abca"，right 走到第二个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) { Map<Character, 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 = 0，right = 0，窗口空。
- right 指向
a，窗口无a，加入，窗口"a"，长度 1。 - right 指向
b，窗口无b，加入，窗口"ab"，长度 2。 - right 指向
c，窗口无c，加入，窗口"abc"，长度 3。 - right 指向
a，窗口中已有a。用 HashSet 版本，left 出发，移除 left 指向的a，left 变成 1，窗口变成"bc"；再加入右边这个a，窗口变成"bca"。长度仍为 3。 - right 指向
b，窗口中已有b。left 从 1 开始移除b，left 变成 2，窗口"ca"，再加入新b，窗口"cab"，长度 3。 - right 指向
c，窗口中已有c。left 从 2 开始移除c，left 变成 3，窗口"ab"，再加入新c，窗口"abc"，长度 3。 - right 指向
b，窗口中已有b。left 从 3 开始移除a，left 变成 4，窗口"bc"，再移除b，left 变成 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时 prevIndex=0，>= left=0，left 直接跳到 1；第三个a时 prevIndex=1，left=1，left 跳到 2，以此类推。每次都是 O(1) 跳转，一气呵成。
第四种边界是字符串包含空格、标点等可见 ASCII 字符。比如"ab b"这种东西。如果用了数组大小为 128 的写法，空格字符的 ASCII 是 32，也在范围内，不影响正确性。但如果字符串中有换行符之类的控制字符，ASCII 码也在 128 以内，同样安全。只有在处理中文或多字节字符的时候，char 的取值可能超过 128，这时就不能直接用int[128]了，需要用int[65536]或者直接用 HashMap。
3.3 一个隐蔽的 bug：prevIndex < left时到底要不要更新左边界
这次我特意写一个容易出错的场景。假设字符串是"abba"。用 HashMap 版本的逻辑来走一遍：
- right=0，
a加入，left=0，maxLen=1。 - right=1，
b加入，left=0，maxLen=2。 - right=2，字符是
b，prevIndex=1，prev>=left，left 跳转到 2。 - right=3，字符是
a，prevIndex=0，此时prevIndex=0 小于 left=2。如果我们不加prev >= left这个判断，而是看见 containsKey 就更新 left=prev+1=1，那么 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 前一百题里最值得反复写的一题，因为它的思想可以顺滑地迁移到后面几十道双指针和字符串题上，多花点时间在上面，绝对不亏。
