企业官网建设流程全解析

刷LeetCode的同学只要点进hot100，前几题里基本都会撞上这道“无重复字符的最长子串”。它排在第3位，难度标着中等，但很多人在面试里被问到的时候，反而容易在边界条件和窗口收缩逻辑上翻车。这道题表面上只是求一个最长子串的长度，实际上考察的是对“滑动窗口”这个高频算法模型的理解程度。不管你是刚开始刷题准备校招，还是工作几年想补一下算法底子，这道题都值得拿出来认真拆一遍。

这篇东西我不打算只贴个答案。我会把暴力解为什么慢、滑动窗口为什么快、两种常见实现路线的差异、以及实际写代码时容易踩的坑全部过一遍，最后用模拟运行的方式带你走完整个匹配过程。看完之后，你不仅能AC这道题，还能顺手把同类问题（比如最长重复字符替换、最小覆盖子串）的解题框架一起打通。

1. 先拆题目：子串、子序列和“窗口”到底在找什么

1.1 题目本质：求的是一个“无重复”的连续区间

先明确一个最基础的概念：子串（substring）必须是连续的，子序列（subsequence）可以不连续。这道题要的是子串，所以像abc在abcabcbb里就是子串，但acb这种跳着取的不算。题目的完整要求是：给定一个字符串，找出其中不含有重复字符的最长子串的长度。

举个例子，输入s = "abcabcbb"时，答案是3，因为abc是最长的无重复子串；输入s = "pwwkew"时，答案是3，对应wke或kew。注意pwke虽然也是无重复字符，但它不是连续的子串，所以不能算。

我看评论区经常有人把“子串”和“子序列”搞混，导致用回溯或者动态规划去解，方向直接跑偏。记住一个判断标准：如果题目里说的是substring，那它一定要求连续；如果题目里说的是subsequence，那才是可以跳着取的。

1.2 暴力解法为什么慢：三重循环的代价

在没有接触过滑动窗口之前，很多人的第一反应是枚举所有子串，然后逐个检查是否有重复字符。也就是两层循环确定子串的起止位置，再用第三层循环或者一个Set去检查这段区间里有没有重复的字符。

int lengthOfLongestSubstring(string s) { int n = s.size(); int ans = 0; for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { unordered_set<char> st; bool ok = true; for (int k = i; k <= j; k++) { if (st.count(s[k])) { ok = false; break; } st.insert(s[k]); } if (ok) ans = max(ans, j - i + 1); } } return ans; }

这段代码的逻辑没错，但时间复杂度是O(n^3)。如果字符串长度是10万，这个量级的计算在LeetCode上基本是超时警告。问题出在哪里？它反复扫描了同一个区间：当我们在检查[i, j]这个区间的时候，[i, j-1]的信息完全可以复用，但暴力解法每次都从零开始重新判断。这就像你打扫房间，明明上一间屋子刚扫过，下一间屋子又要从门口重新扫一遍，大量重复劳动。

1.3 滑动窗口的直觉来源：维护一个动态区间

滑动窗口的思路其实来源于一个很朴素的观察：如果从左边界i到右边界j这段区间里没有重复字符，那么我们把右边界继续向右扩展的时候，只需要判断新加入的字符是否和当前区间里的字符重复；如果重复了，就移动左边界，直到区间内不再包含这个重复字符为止。

这个过程中，区间就像一个长度可变的窗口，它在字符串上从左往右滑动，窗口内的字符始终保持“无重复”。我们要做的，就是在窗口滑动的过程中，记录下窗口曾经达到的最大长度。窗口不需要回退，左边界和右边界都只向右移动，所以每个字符最多被访问两次（一次进窗口，一次出窗口），整体复杂度是O(n)。

2. 滑动窗口的核心：两个指针、一个容器、一套收缩逻辑

2.1 窗口的扩张与收缩机制

滑动窗口通常用两个指针表示：left指向窗口的左边界，right指向窗口的右边界。初始时，left = 0，right = 0，窗口是空的。接着right不断向右移动，每次移动都把s[right]这个字符加入窗口，同时检查窗口中是否已经存在这个字符。

如果不存在，说明当前窗口依然合法，更新最大长度。如果存在，说明遇到重复了，这时需要移动left，把左边界向右收缩，直到窗口内不再包含重复的那个字符为止。收缩完成后，再把right位置的字符正常加入窗口。

这里有一个很多人第一次写会犯的错误：收缩完成之后，忘了把新字符加进窗口，或者收缩的条件写错，导致窗口内的字符集合和实际区间对不上。记住一点，left和right描述的是一个闭区间[left, right]，每次right移动后，这个区间内的字符都应该和容器里记录的内容保持一致。

2.2 两种容器选择：HashSet与HashMap

实现滑动窗口的时候，容器有两种常见选择。

第一种，使用HashSet配合left逐个收缩。当发现s[right]已经在集合里时，就循环移除s[left]，并让left++，直到集合里不再包含s[right]，然后把s[right]加进集合。这种写法逻辑清晰，适合用来理解滑动窗口的工作过程。

int lengthOfLongestSubstring(string s) { int n = s.length(); unordered_set<char> st; int left = 0, ans = 0; for (int right = 0; right < n; right++) { while (st.count(s[right])) { st.erase(s[left]); left++; } st.insert(s[right]); ans = max(ans, right - left + 1); } return ans; }

第二种，使用HashMap（字符到索引的映射）。当遇到重复字符时，不需要left一步一步走，而是直接跳到重复字符上次出现位置的下一个位置。这种写法更快，但细节上更容易出错。

int lengthOfLongestSubstring(string s) { int n = s.length(); unordered_map<char, int> mp; int left = 0, ans = 0; for (int right = 0; right < n; right++) { char c = s[right]; if (mp.count(c) && mp[c] >= left) { left = mp[c] + 1; } mp[c] = right; ans = max(ans, right - left + 1); } return ans; }

我个人的建议是：面试时先用HashSet版本讲清楚思路，如果面试官追问优化，再给出HashMap版本。两个版本的时间复杂度都是O(n)，但HashMap版本在极端情况下（比如长字符串且重复少）会快一些，因为左边界可以直接跨越，不用逐个挪动。

3. 代码实现与逐步模拟：从空窗口到最大长度

3.1 一份可以直接跑的完整实现

下面是我在实际刷题中比较常用的一种写法，使用HashSet，全程只需要一个while循环加一个for循环，逻辑很直白：

function lengthOfLongestSubstring(s) { const set = new Set(); let left = 0; let maxLen = 0; for (let right = 0; right < s.length; right++) { const ch = s[right]; while (set.has(ch)) { set.delete(s[left]); left++; } set.add(ch); maxLen = Math.max(maxLen, right - left + 1); } return maxLen; }

这个实现有什么特点？它每次遇到重复字符时，删除的是窗口最左边的字符，而不是直接去删重复的那个字符。原因很简单：我们维护的是一个连续区间，只有从左边逐个移除，才能保证区间内剩下的字符仍然是连续的。如果直接删除重复字符，中间会留下“空洞”，区间就不连续了。

3.2 手动推演一遍：s = "abcabcbb"

我们拿最经典的用例abcabcbb来走一遍流程，看看窗口是怎么变化的。

1. 初始：left = 0，right = 0，窗口[]，集合{}。
2. right = 0，字符a不在集合里，加入集合{a}，窗口[0,0]，长度1，maxLen=1。
3. right = 1，字符b不在集合里，加入集合{a,b}，窗口[0,1]，长度2，maxLen=2。
4. right = 2，字符c不在集合里，加入集合{a,b,c}，窗口[0,2]，长度3，maxLen=3。
5. right = 3，字符a在集合里，进入while循环：删除s[0]=a，left=1，集合变成{b,c}；此时a不在集合里了，退出循环。加入a，集合{b,c,a}，窗口[1,3]，长度3，maxLen=3。
6. right = 4，字符b在集合里，删除s[1]=b，left=2，集合{c,a}；b不在集合里了，加入b，集合{c,a,b}，窗口[2,4]，长度3，maxLen=3。
7. right = 5，字符c在集合里，删除s[2]=c，left=3，集合{a,b}；c不在集合里了，加入c，集合{a,b,c}，窗口[3,5]，长度3，maxLen=3。
8. right = 6，字符b在集合里，删除s[3]=a，left=4，集合{b,c}；b还在集合里，继续删除s[4]=b，left=5，集合{c}；b不在集合里了，加入b，集合{c,b}，窗口[5,6]，长度2，maxLen=3。
9. right = 7，字符b在集合里，删除s[5]=c，left=6，集合{b}；b还在集合里，继续删除s[6]=b，left=7，集合{}；加入b，集合{b}，窗口[7,7]，长度1，maxLen=3。

最终结果为3。整个过程里，left一直在向右走，没有回头，这就是滑动窗口“摊还O(n)”的来源。

3.3 复杂度分析：为什么它是O(n)而不是O(n^2)

有人会问：while循环里不是可能连续删除很多个字符吗？为什么整体复杂度还是O(n)？

关键点在于：每个字符最多被加入集合一次，也最多被删除一次。right指针遍历整个字符串，每个字符都会进入集合一次；left指针虽然有可能连续移动，但它总共移动的次数不会超过n次，因为left不可能超过right。所以整体的操作次数大概是2n，时间复杂度是O(n)，空间复杂度是O(min(n, 字符集大小))。

这个“每个元素最多进一次、出一次”的摊还分析思路，是理解滑动窗口复杂度的核心。以后遇到其他滑动窗口题目，也可以用同样的方法去估算复杂度。

4. 容易翻车的边界条件和常见问题

4.1 空字符串、全重复、全不重复

写这道题，边界条件测试是必须的。我一般会固定测这几组用例：

• s = ""，答案是0。
• s = " "，答案是1，注意空格也是一个字符。
• s = "bbbbb"，答案是1，所有字符都相同。
• s = "au"，答案是2。
• s = "dvdf"，答案是3，对应vdf。

其中dvdf这个用例比较有迷惑性：如果顺着暴力思路，可能第一次找到d、v、d三个字符时就以为到头了，但实际上跳过第一个d之后，vdf才是答案。滑动窗口的收缩逻辑会自动处理这个过程：当遇到第二个d时，left移动到第一个d之后，窗口变成vdf，长度3。

4.2 试着试着就忘掉的细节

写代码时最容易出问题的有几个地方。

第一个是HashMap版本里的mp[c] >= left这个判断。为什么不能只写mp.count(c)？因为mp里可能保存着一些已经不在窗口内的旧索引。比如s = "abba"，当你处理到第二个b时，left已经变成了2，但mp里还保存着第一个a的索引0。如果你只看mp.count('a')，就会错误地把left回退到1，导致答案错误。所以必须加上mp[c] >= left，确保你跳转的位置在窗口内部才会生效。

第二个是在HashSet版本里，while循环里必须先删除left位置的字符，再让left++。顺序反过来会导致删除的字符和移动的边界不一致。

第三个是更新最大长度的时机。我见过有人把更新放在left移动之前，这样处理重复字符时可能会产生错误的更大值。比如s = "abca"，处理到最后一个a时，窗口长度是4，但此时窗口内有重复，所以不应该用这个长度更新答案。正确做法是收缩完窗口、加入新字符之后再更新。

4.3 实际刷题中的调试技巧

如果你提交后出现答案错误，我建议在代码里加一行输出：每次right移动结束后，打印left、right、窗口长度和当前的集合内容。比如：

cout << "left=" << left << ", right=" << right << ", len=" << right - left + 1 << endl;

这样你就能直观地看到窗口的收缩过程，问题一般出在“收缩前更新答案”或者“收缩条件写错”这两类情况里。我当初刷这道题时，就是因为没有加mp[c] >= left这个判断，在abba上连续错了两三次，打印日志后才彻底明白问题出在哪。这个教训很值得记下来：HashMap版本的滑动窗口，边界跳转必须搭配位置判断。

5. 从这一题到一类题：滑动窗口的迁移经验

这道题做熟之后，最大的收益不是AC了一个中等题，而是掌握了“可变窗口”的通用套路。LeetCode上很多中等题的核心框架都长得很像：右边界扩大窗口，窗口不满足条件时收缩左边界，更新答案的时机根据题目要求放在不同位置。

比如424. 替换后的最长重复字符，核心是维护一个窗口，保证窗口内“非主流字符”的数量不超过k；76. 最小覆盖子串则需要用两个计数器维护窗口内字符是否满足覆盖条件。它们的本质都是：用一个容器记录窗口状态，在右边界扩张和左边界收缩之间找到满足条件的窗口。

我的建议是，刷完这道题后，可以试着用同样的框架去解LeetCode 209. 长度最小的子数组和LeetCode 1004. 最大连续1的个数 III。这两题和本题的区别在于，它们的窗口不需要用HashSet，只需要维护窗口和或者计数，但思考方式完全一致。

最后再说一个我个人的小习惯：我刷这道题时，会额外写一个暴力解作为对拍程序，随机生成小写字母字符串，用滑动窗口的结果和暴力结果做对比。虽然LeetCode测试用例已经很全面，但对拍可以帮你快速定位一些意想不到的错误场景，尤其是HashMap版本里索引跳转的边界问题。这个方法看起来土，但排查效率非常在线。

如果你能把这题的两种写法都熟练到可以默写，并且把为什么HashMap版本要判断mp[c] >= left讲清楚，那面试官基本就能判定你对滑动窗口这一块是真正理解了。这道hot100的第3题，值得你花这个时间。