刷 LeetCode 100 题计划走到第四天手感明显和第一天不一样了。今天啃的是热门 100 题里非常经典的一道——无重复字符的最长子串题目编号第 3 题。这题在评论区经常能看到两拨人一波觉得“不就是个 HashMap 嘛”另一波觉得“边界条件怎么老是写错”。其实这道题考的是滑动窗口这个大类里最基础的模型把窗口的伸缩逻辑想透了后面遇到一堆同源题都能顺手解掉。这篇笔记我会从暴力解开始一步步优化到 O(n) 的版本再把刷题过程中容易踩的坑全部摆出来。适合刚刷完双指针、准备系统性过 LeetCode 100 题的同学参考。1. 题目拆解这个“最长”到底长在哪1.1 三个例子把题意钉死题目描述非常短给定一个字符串s找出其中不含有重复字符的最长子串的长度。但短题往往暗藏杀机尤其是“子串”两个字。看第一个例子abcabcbb答案为什么是 3因为最长的不含重复字符的连续片段是abc长度 3。很多人第一眼会想abc后面还能不能接着取bca不能题目要求的是连续子串不是子序列。子序列可以跳着选子串必须是完整挨着的一段。这个区别如果不注意后面做题很容易跑偏。第二个例子pwwkew答案是 3对应wke或kew。这里容易踩一个误区有人会觉得pwke不是也行吗但pwke跳过了中间重复的w是子序列不是子串。看题的时候一定记住遇到“子串”两个字第一反应就是连续区间。第三个例子dvdf是经典的易错用例。刚上手的人会觉得最长是 2因为直观上看dv和df都是长度为 2 的无重复子串。但正确答案是 3对应vdf。窗口需要从d移到v也就是说当右指针扫描到最后一个d时左指针不能还停在第一个字符上。这个例子最能说明滑动窗口的“跳跃感”后面手推过程时会详细展开。1.2 为什么这题在热门 100 里地位特殊LeetCode 热门 100 题列表里这题被归在“哈希表”和“字符串”标签下实际上它还横跨了“滑动窗口”。这三个标签在面试中的出现频率都非常高尤其是大厂一面二面经常拿它当热身题。这道题的特殊性在于它不要求你掌握什么高深的算法也不涉及复杂的数据结构但非常考验对“区间合法性”的理解。很多人写得出代码但说不太清楚为什么left可以一下跳那么远还有很多人能背下题解换一道变体就不会了。所以与其说这题考编码不如说考你能不能把一个连续区间的变化过程建模清楚。刷题社区里有一句话我特别认同“滑动窗口好讲但写对的人不多。”原因就在于窗口的边界条件、左指针的更新时机、存储结构的选择这些细节环环相扣。把这道题彻底讲清楚后面做“最小覆盖子串”“最长重复字符替换”这些题会省力非常多。2. 从暴力枚举到滑动窗口的演进路径2.1 暴力解先确认“能跑”再谈“跑得快”拿到一道题如果时间不算紧迫我的习惯是先写一个暴力解确认自己的思路没有理解偏差再考虑优化。这道题的暴力思路非常直接枚举所有子串的起点和终点然后检查这个子串里有没有重复字符。def length_of_longest_substring_brutal(s: str) - int: n len(s) ans 0 for i in range(n): for j in range(i, n): # 判断 s[i:j1] 是否包含重复字符 sub s[i:j1] if len(set(sub)) len(sub): ans max(ans, j - i 1) return ans这个写法的问题一眼就能看出来外层枚举起点 O(n)内层枚举终点 O(n)set判断内部又是 O(n)整体复杂度 O(n^3)。在 LeetCode 上跑一个中等长度的字符串就直接超时。但暴力解也不是没有价值。它帮我们确定了答案的形式子串一定是从某个位置i开始、到某个位置j结束的连续片段。我们优化的目标是怎么减少枚举的次数以及怎么快速判断窗口内是否有重复。如果暂时不允许 O(n^3)可以优化掉set改成一边扩展终点一边维护一个计数器这时枚举起点后终点可以不用回溯复杂度降到 O(n^2)。但 O(n^2) 在 n 到 10^5 级别时依然跑不动所以还得继续往下走。2.2 关键观察重复字符触发左指针跳跃我梳理这个问题的时候把注意力放在了一个现象上当右指针扩展到一个已经出现过的字符时窗口一定需要收缩。问题是收缩多少看一个最直白的例子abcabcbb。当右指针扫描到第二个a时当前窗口是abca左指针在 0。这时候为了去掉重复的a左指针应该挪到哪里答案是第一个a的下一个位置也就是下标 1。挪完之后窗口变成bca合法且不丢结果。这个观察太关键了左指针没有必要一步一步往右挪它可以直接跳到“重复字符在窗口内上一次出现位置 1”。这样窗口的收缩就是 O(1) 的整体扫描过程只需要右指针从左到右走一遍。我自己想这件事的时候打了个比方就像排队买奶茶队伍里有一个你之前见过的人新来的这个人又想排进队。为了保证队伍里没有重复的人队首必须一直往前进直到越过之前那个和你见过的人。整条队伍只会往右移动不会倒退这就是滑动窗口的灵魂。2.3 滑动窗口的适用条件这个题解完之后值得停下来思考一下为什么滑动窗口在本题有效因为这个问题满足一个重要的单调性当右指针扩展导致窗口不合法时左指针只能右移而且右移之后窗口的合法性不会变得更差。换句话说一旦某个字符造成了重复左指针跳到重复位置之后窗口就恢复合法右指针不需要回退因为从当前位置往后的最长合法区间一定是以一个新的起点开始的。反过来说如果一个问题的窗口合法性不满足这种“单调收缩”性质比如左指针右移也可能让情况变糟那滑动窗口就不适用了得另想办法。这也是为什么后面做变体题时要先确认窗口的收缩逻辑是否符合单调性。3. 主方案哈希表记录下标右指针一路往前走3.1 为什么用哈希表而不是哈希集合很多人一看到“无重复字符”第一反应是用Set存窗口里的字符。用Set确实能判断有没有重复但它回答不了“重复的那个字符到底在哪个位置”这个问题。不知道位置左指针就没法跳跃只能慢慢删。所以这里要用MapCharacter, Integer把每个字符最后一次出现的位置记下来。这样当右指针扫到某个字符c时直接从 map 里查出c上一次出现的位置如果它还在窗口内就把左指针跳过去。有一个细节必须强调判断重复时不能只看map.containsKey(c)还要看map.get(c) left。因为 map 保存的是整个字符串扫描过程中的历史位置有些字符虽然之前出现过但那个位置已经在窗口之外了它并不构成当前窗口的重复。比如abba扫描到最后一个a时map 里a的位置是 0但此时left已经变成了 20 2说明这个a已经出了窗口不影响。3.2 Java 与 Python 双版本实现先看 Java 版class Solution { public int lengthOfLongestSubstring(String s) { MapCharacter, Integer map new HashMap(); int left 0; int ans 0; for (int right 0; right s.length(); right) { char c s.charAt(right); if (map.containsKey(c) map.get(c) left) { left map.get(c) 1; } map.put(c, right); ans Math.max(ans, right - left 1); } return ans; } }再贴一个 Python 版本def length_of_longest_substring(s: str) - int: last_pos {} left 0 ans 0 for right, ch in enumerate(s): if ch in last_pos and last_pos[ch] left: left last_pos[ch] 1 last_pos[ch] right ans max(ans, right - left 1) return ans两个版本的逻辑完全一致。核心流程拆开看就是三步右指针前进遇到重复字符就把left跳到上一个相同字符位置 1然后更新当前字符的最新位置并计算窗口长度。需要注意顺序先判断、再跳left、最后才执行map.put(c, right)。如果先更新了位置再用它和left比较等于拿“当前这次出现的位置”和窗口左边界比永远都满足 leftleft会被错误地推到右指针后面整个答案直接崩掉。3.3 三个用例手推过程光看代码可能不够直观我用手推一遍最典型的abcabcbb。下表列出每一步的状态right字符进入前窗口map 中该字符位置left 跳转更新后窗口ans0a[0,0]-无需跳转[0,0]11b[0,1]-无需跳转[0,1]22c[0,2]-无需跳转[0,2]33a[0,3]0left1[1,3]34b[1,4]1left2[2,4]35c[2,5]2left3[3,5]36b[3,6]1 (已出窗口)不跳[3,6]37b[3,7]6left7[7,7]3注意第 6 步字符b确实在 map 里出现过但位置是 1小于当前left3说明这个b已经在窗口外面了不构成重复所以left不动。再看pwwkewright字符left 变化ans0pleft011wleft022wleft 跳到 313kleft324eleft335wleft 跳到 4因为 w 上次位置是 223跳 213最后是dvdf这个例子特别能说明 left 跳跃的精彩之处right字符left 变化窗口ans0dleft0[0,0]11vleft0[0,1]22dleft 跳到 1[1,2]23fleft1[1,3]3注意第 2 步 left 从 0 跳到 1窗口变成vd第 3 步加入f后窗口是vdf长度 3。如果当初采用的是“遇到重复就 left”那中间会浪费大量迭代而且容易写出 bug。3.4 复杂度分析时间复杂度是 O(n)因为右指针从左到右扫一遍left 也只增不减两个指针的总移动次数不会超过 2n。空间复杂度严格说是 O(min(n, |Σ|))其中 |Σ| 是字符集大小。map 里最多存当前窗口内的字符或者整个字符串里出现过的不同字符。对 ASCII 字符集来说|Σ| 通常看作常数所以很多题解直接写 O(1)。但如果题目明确是 Unicode 字符理论上存储规模会随字符集变大面试里建议说清楚这一点反而显得你考虑周全。4. 用数组替换 HashMap常数小一半的优化写法4.1 字符集是有限集合数组就是天然的哈希表HashMap 用起来方便但它内部有哈希计算、链表/红黑树、装箱拆箱这些开销。如果在面试现场或者追求极致性能还有一个更轻的方案用数组模拟哈希表。因为字符的编码天然就是一个整数对于常见的 ASCII 可见字符范围是 0 到 127扩展 ASCII 是 0 到 255。我们可以开一个int[128]或者int[256]下标就是字符本身值就是该字符最后一次出现的下标。初始全部填充为 -1表示没出现过。class Solution { public int lengthOfLongestSubstring(String s) { int[] last new int[128]; Arrays.fill(last, -1); int left 0; int ans 0; for (int right 0; right s.length(); 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; } }这个版本省去了containsKey的判断因为数组初始化就是 -1而 left 最小也是 0所以last[c] left天然包含了“之前出现过且在窗口内”的语义。为什么能这么换因为字符这件事本身就是离散且范围有限的。HashMap 的本质是键到值的映射而在这里键恰好是一个可以当数组下标的整数数组就成了最直接的哈希表而且没有碰撞问题。4.2 加一点“窗口模板”的肌肉记忆刷到第 4 天我发现自己最需要的不只是某一道题的答案而是一套可以迁移的框架。滑动窗口里最常见的是可变窗口模板伪代码如下right 从 0 到 n-1 遍历 将 s[right] 加入窗口 while 窗口不合法 移除 s[left] left 更新答案本题比较特殊的地方在于窗口不合法的修复不需要 while 循环只需要一个 if 就能跳到目标位置。因为left跳过去之后窗口内一定没有重复了不需要逐格调整。但在使用Set的写法里修复过程通常是int left 0; SetCharacter set new HashSet(); int ans 0; for (int right 0; right s.length(); right) { while (set.contains(s.charAt(right))) { set.remove(s.charAt(left)); left; } set.add(s.charAt(right)); ans Math.max(ans, right - left 1); }这个版本逻辑也正确但注意一定要用while而不是if。举个反例abcb当 right3 指向第二个b时set里是{a, b, c}left0。如果写成if只移除aleft 变成 1set变成{b, c}然后执行add(b)窗口变成{b, c, b}仍然有重复但 ans 已经错误更新了。所以用 Set 就必须 while 循环。相比之下用哈希表记录下标的写法天然是跳跃式的更优雅也更能讲清楚原理。4.3 变体练习一通百通的同源题这道题刷完之后强烈建议顺手做几个变体都是同一套窗口框架至多包含两个不同字符的最长子串LeetCode 159窗口合法条件从“无重复字符”变成“不同字符数 2”。需要维护一个计数器或者 map 统计窗口内每个字符的出现次数收缩时对应的计数减到 0 就移除 key。至多包含 K 个不同字符的最长子串LeetCode 340上面那题的泛化把 2 改成 K答题思路一模一样。长度为 K 的无重复字符子串个数LeetCode 1100这时候窗口大小固定为 K需要统计的是满足无重复条件的窗口数量。最小覆盖子串LeetCode 76同样是可变窗口但窗口合法条件是“包含目标串所有字符”且每次更新答案时取最小长度。做这些变体时你会发现套模板最关键的是想清楚两件事窗口的合法性条件是什么以及答案在什么时机更新。搞清这两点题就完成了一大半。5. 刷这道题时最容易写错的三个地方5.1 忘加 containsKey空指针就在眼前用 Java 写 Map 版本时很容易写出这样的代码if (map.get(c) left) { left map.get(c) 1; }这段代码在c不存在时报错吗不一定报错取决于map.get(c)返回的null是否和left进行比较。Java 中Integer会自动拆箱null拆箱直接触发NullPointerException。这是非常容易踩的坑尤其在面试手写代码时紧张状态下极容易漏。修正方法有两种if (map.containsKey(c) map.get(c) left) { left map.get(c) 1; }或者用getOrDefaultif (map.getOrDefault(c, -1) left) { left map.get(c) 1; }第二个写法的好处是一行解决不需要containsKey的短路判断逻辑也更紧凑。5.2 Set 写法的 while 陷阱前面已经提到过abcb这个反例。用Set判断窗口内容很简单但修复重复需要逐个删除窗口左边界的字符而且必须是 while直到当前字符不在集合中为止。这个坑之所以隐蔽是因为很多人写if时测试用例恰好是abcabcbb这种重复字符都在窗口尾部的情况侥幸跑通了。一旦换成abcb答案就会比正确值大。我在本地跑测试的时候就是被这种“看似正确但边界出错”的用例坑了一晚上。如果你现在功力还没到能一眼区分if和while我的建议是优先使用 Map 记录下标的版本它的 left 跳跃是确定的不会掉进这种陷阱。5.3 left 更新顺序错了也不行还有一次我把代码写成了这样map.put(c, right); if (map.get(c) left) { left map.get(c) 1; }先 put 再判断问题很大put 之后 map 里这个字符的位置已经变成当前 right 了map.get(c) left恒成立于是 left 会被跳到 right1ans 变成 1然后下一轮右指针继续走left 还是被错误地拉着走导致答案一直偏小。正确顺序必须是先基于旧位置判断重复再更新位置。这个顺序问题在面试里也很容易被问最好在写的时候就直接按“判断、跳转、更新”的顺序写形成肌肉记忆。6. 把这道题讲给面试官听一种可复制的讲解节奏6.1 先抛出暴力解再讲优化面试的时候如果一上来就写最优解很多面试官反而会怀疑你是背的。比较好的节奏是先说最直观的暴力解法 O(n^3)然后指出问题是重复判断太慢再提 O(n^2) 的优化方向最后给出滑动窗口 哈希表的 O(n) 方案。这样做有两个好处。第一展示了你的思考路径面试官会觉得你在“解题”而不是“背题”。第二万一最优解里某个边界条件说错了前面铺垫的思路可以帮你有机会补救不至于完全卡死。6.2 写代码时重点讲两个变量我自己的经验是讲到滑动窗口时一定要把left和map的含义说透left表示当前窗口的左边界窗口是[left, right]。map记录的是“每个字符最近一次出现的下标”不是“是否出现过”。当右指针到c时如果c上一次出现的位置在窗口内就说明窗口不合法需要把左边界直接跳到那个位置 1。这个过程要配合一个例子讲比如拿dvdf现场画一下 left 的跳跃轨迹面试官很容易跟上。6.3 如果被追问“还能再优化吗”顺着数组版本讲。把Map换成一个长度 128 或 256 的数组初值设为 -1判断逻辑完全不变。这个优化在数据量巨大时才看得出差异但能展示你知道底层数据结构在不同场景下的取舍。一般讲到这一步已经足够面试官很少会继续追下去。如果继续追问字符集是 Unicode 怎么办那就解释int[65536]也能覆盖大部分字符但稀疏情况下用Map更省内存这就是空间和时间的权衡。6.4 周赛里的同源题模板真的能救急前几天参加周赛遇到一道题场景包装成了字符串替换核心仍然是维护一个窗口满足某种计数条件。我当时直接把滑动窗口的模板改了两行就过了那种感觉比背十个题解都踏实。这也是为什么我一直建议刷 LeetCode 百题计划里的基础题时不要只求 AC要把模板的适用条件和边界写明白。这道题算是滑动窗口的“元题”后面周赛里大量出现和它神似的题目。唯一不同的是周赛题往往套了一层业务场景的壳让你先识别出“这是在求满足条件的连续区间”然后就能直接套模板。我自己把这道题刷完后的习惯是把上面那张手推状态表也放在笔记里每次忘了 left 跳跃的原理就翻出来看一眼。做这种基础题慢一点没关系手推一遍比看十遍答案都管用。如果你能把dvdf的 left 跳变过程给一个完全没做过这道题的人讲明白这题就真正吃透了。