企业官网建设流程全解析

刷 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:j+1] 是否包含重复字符 sub = s[i:j+1] 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确实能判断有没有重复，但它回答不了“重复的那个字符到底在哪个位置”这个问题。不知道位置，左指针就没法跳跃，只能慢慢删。

所以这里要用Map<Character, Integer>，把每个字符最后一次出现的位置记下来。这样当右指针扫到某个字符c时，直接从 map 里查出c上一次出现的位置，如果它还在窗口内，就把左指针跳过去。

有一个细节必须强调：判断重复时不能只看map.containsKey(c)，还要看map.get(c) >= left。因为 map 保存的是整个字符串扫描过程中的历史位置，有些字符虽然之前出现过，但那个位置已经在窗口之外了，它并不构成当前窗口的重复。比如abba，扫描到最后一个a时，map 里a的位置是 0，但此时left已经变成了 2，0 < 2，说明这个a已经出了窗口，不影响。

3.2 Java 与 Python 双版本实现

先看 Java 版：

class Solution { public int lengthOfLongestSubstring(String s) { Map<Character, 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比较，等于拿“当前这次出现的位置”和窗口左边界比，永远都满足>= left，left会被错误地推到右指针后面，整个答案直接崩掉。

3.3 三个用例手推过程

光看代码可能不够直观，我用手推一遍最典型的abcabcbb。下表列出每一步的状态：

注意第 6 步，字符b确实在 map 里出现过，但位置是 1，小于当前left=3，说明这个b已经在窗口外面了，不构成重复，所以left不动。

再看pwwkew：

最后是dvdf，这个例子特别能说明 left 跳跃的精彩之处：

注意第 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; Set<Character> 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，当 right=3 指向第二个b时，set里是{a, b, c}，left=0。如果写成if，只移除a，left 变成 1，set变成{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; }

或者用getOrDefault：

if (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 会被跳到 right+1，ans 变成 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 跳变过程给一个完全没做过这道题的人讲明白，这题就真正吃透了。