刷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_setchar 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 0right 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_setchar 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_mapchar, 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来走一遍流程看看窗口是怎么变化的。初始left 0right 0窗口[]集合{}。right 0字符a不在集合里加入集合{a}窗口[0,0]长度1maxLen1。right 1字符b不在集合里加入集合{a,b}窗口[0,1]长度2maxLen2。right 2字符c不在集合里加入集合{a,b,c}窗口[0,2]长度3maxLen3。right 3字符a在集合里进入while循环删除s[0]aleft1集合变成{b,c}此时a不在集合里了退出循环。加入a集合{b,c,a}窗口[1,3]长度3maxLen3。right 4字符b在集合里删除s[1]bleft2集合{c,a}b不在集合里了加入b集合{c,a,b}窗口[2,4]长度3maxLen3。right 5字符c在集合里删除s[2]cleft3集合{a,b}c不在集合里了加入c集合{a,b,c}窗口[3,5]长度3maxLen3。right 6字符b在集合里删除s[3]aleft4集合{b,c}b还在集合里继续删除s[4]bleft5集合{c}b不在集合里了加入b集合{c,b}窗口[5,6]长度2maxLen3。right 7字符b在集合里删除s[5]cleft6集合{b}b还在集合里继续删除s[6]bleft7集合{}加入b集合{b}窗口[7,7]长度1maxLen3。最终结果为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. 替换后的最长重复字符核心是维护一个窗口保证窗口内“非主流字符”的数量不超过k76. 最小覆盖子串则需要用两个计数器维护窗口内字符是否满足覆盖条件。它们的本质都是用一个容器记录窗口状态在右边界扩张和左边界收缩之间找到满足条件的窗口。我的建议是刷完这道题后可以试着用同样的框架去解LeetCode 209. 长度最小的子数组和LeetCode 1004. 最大连续1的个数 III。这两题和本题的区别在于它们的窗口不需要用HashSet只需要维护窗口和或者计数但思考方式完全一致。最后再说一个我个人的小习惯我刷这道题时会额外写一个暴力解作为对拍程序随机生成小写字母字符串用滑动窗口的结果和暴力结果做对比。虽然LeetCode测试用例已经很全面但对拍可以帮你快速定位一些意想不到的错误场景尤其是HashMap版本里索引跳转的边界问题。这个方法看起来土但排查效率非常在线。如果你能把这题的两种写法都熟练到可以默写并且把为什么HashMap版本要判断mp[c] left讲清楚那面试官基本就能判定你对滑动窗口这一块是真正理解了。这道hot100的第3题值得你花这个时间。
