“求字符串中不重复的最长子串的长度”光看这个题目你可能觉得平平无奇但它在算法题单里的地位相当特殊LeetCode 原题编号第 3 题。我面试别人的时候喜欢拿它当开场题带新人刷题也习惯先让写这一道。它看起来就是字符串处理实际上背后是双指针加哈希表的经典组合吃透这一题后面一连串滑动窗口变种题都能顺带拿下。这篇文章我不打算只贴一个能过评测的答案而是想从头讲清楚几个问题暴力解法为什么不行滑动窗口是怎么自然推出来的left 指针到底该往哪跳以及 C 实现里有哪几个不写进去就会翻车的细节。适合第一次接触滑动窗口的新手、准备面试刷题的同学以及那些想把代码从“能跑”打磨到“稳定又高效”的进阶读者。1. 先看懂题这道题到底在问什么1.1 子串和子序列是两种完全不同的东西题目说的是“最长子串”不是“最长子序列”。这两个词在面试里如果听岔了代码会完全不一样。子串要求连续也就是说你切出来的这一段必须原封不动地在原字符串里挨着出现子序列则允许跳着挑字符。举个例子字符串abcabcbb最长无重复子串是abc或者bca长度都是 3。但是最长无重复子序列可以挑成abc拼上后面的abc吗不行那里面有重复字符。实际上子序列版本要另算题目比子串简单不少因为不需要维护连续性。我们这道题的核心难点恰恰就是这个“连续”带来的窗口约束。还有一个容易忽略的前提字符重复是说在选中的这一段里没有出现两次相同的字符。比如pwwkew答案是wke或kew长度 3但pwke不是答案虽然长度也是 3而且看着更“完整”因为它在原串里是子序列但不是连续子串。1.2 暴力解法其实没那么不堪但确实撑不住拿到这道题正常人第一反应都是枚举所有子串逐个检查里面有没有重复字符。检查方式也直接搞一个集合往里塞字符如果发现塞不进去就说明有重复。枚举起点i终点j然后 O(len) 检查整体复杂度 O(n³)。这个复杂度在字符串长度几千的时候还能忍但一旦到几万就开始卡LeetCode 上这题的测试用例轻松到十几万O(n³) 直接超时。我见过有人写出两层循环的“伪优化版本”枚举所有起点然后从起点往后尽量扩展边扩展边检查重复。这个其实已经是 O(n²) 了但面对十万级长度的用例照样挂。面试官看到这种答案一般会点点头然后问一句“能不能 O(n)”这时候就得拿出滑动窗口了。1.3 一个朴素观察窗口的右边界不需要回退我们想象自己手里拿着一个放大镜从左往右扫描字符串放大镜框住一段“当前窗口”窗口里的字符都互不相同。随着右边界往右走新字符可能和窗口里的某个旧字符撞车。如果撞车我们当然可以把左边界往右挪直到把冲突的那个字符挤出去。但这里有一个关键点左边界永远不需要往左回移。因为窗口变短之后即使后面再找到更长的窗口起点也不可能比当前这个左边界更靠左了。一旦窗口起点往右挪它就再也回不去了。这个单调性就是滑动窗口算法能成立的根基。你不需要像暴力法那样重新枚举起点只要维护一个“只往右走”的左边界和一个“只往右走”的右边界两个人配合着前进所有可能的窗口起点都覆盖到了。这个思路听起来简单但怎么把“冲突之后左边该滑到哪”处理对才是这道题真正的分水岭。2. 滑动窗口解法的完整推导2.1 窗口的语义一段无重复字符的连续区间用两个索引left和right表示当前窗口区间前闭后闭也就是[left, right]这一段都是合法无重复的。right每往前多扫一个字符就先判断这个字符是不是已经在窗口里出现过。如果没有出现过窗口直接扩张也就是right窗口长度变大用当前长度尝试更新答案。如果出现过就要动left了。这里的“出现过”要解释清楚是出现在当前窗口里还是出现在整个扫描历史里这两个说法在不同写法里都有对应的实现。如果只判断“整个历史出现过”那left的更新就要配合历史位置信息如果判断“当前窗口里出现过”那就要维护窗口内的字符集合。两种都能得到正确答案但代码手感和面试观感差别很大。我用过窗口内集合的做法也用过历史位置的做法最终推荐后面一种。因为它不需要在left移动时去集合里删除字符逻辑上更简洁而且能把每次left跳转变得更激进甚至是直接跳跃而不是一格一格挪。2.2 收缩时到底跳到哪里max 是防回退的关键假设扫描到right位置的字符是c并且在更早的位置pos也出现过一次c。如果pos还在当前窗口[left, right-1]里面说明冲突了那窗口的左边界至少得变成pos 1把这个旧的c隔到窗口外。如果pos已经不在当前窗口里了说明那个重复字符早就被滑出去了当前这个c是安全的left不需要动。所以正确的更新写法是left max(left, lastPos[s[right]] 1);这里的max很容易被漏掉。漏掉之后会出现什么情况用一个经典例子abba就能解释。扫描到最后一个a的时候lastPos[a]第一次出现在位置 0但当前left已经滑到 2 了因为中间处理过两个b的冲突。如果不取maxleft会被更新成 1窗口变成[1, 3]也就是bba里面就有重复的b了计算结果直接错。所以一定要让left只会变大、不会变小这个max就是那堵防回退的墙。我个人第一次写这个题就栽在漏max上当时调试了很久输出老是多了 1一度以为是哈希表更新时机的问题后来才定位到是left回退了。这个坑非常典型后面调试实录里详细展开。2.3 为什么说复杂度是严格 O(n)很多人以为滑动窗口就是两个循环套在一起最坏会是 O(n²)但其实是 O(n)。原因在于left和right都只会单调递增right每轮循环最多走一步left在整个过程中最多也只会走 n 步。每个字符最多被right碰到一次、被left越过一次常数乘 2仍然是线性复杂度。对比一下“窗口内用集合 逐格收缩”的写法虽然也是 O(n)但left是逐个字符往外挪的极端情况比如所有字符都一样窗口会不断收缩再扩张字符被访问次数会变成 2n。用跳跃式更新之后left可以一次性跳到冲突位置的下一个位置省掉中间无意义的比较。从工程角度看这就是“推理正确”和“代码高效”之间的一个平衡点。3. C 代码实现与细节打磨3.1 第一版能跑的代码用 unordered_map 记录字符位置直接给一份能过评测的 C 实现这也是我推荐新手先写出来的版本class Solution { public: int lengthOfLongestSubstring(string s) { unordered_mapchar, int lastPos; int left 0; int ans 0; for (int right 0; right s.size(); right) { char c s[right]; if (lastPos.count(c) lastPos[c] left) { left lastPos[c] 1; } lastPos[c] right; ans max(ans, right - left 1); } return ans; } };这里判断重复的条件是lastPos.count(c) lastPos[c] left意思是“这个字符出现过并且上次出现位置还在当前窗口里”。也可以用我前面写的另一种写法先无条件left max(left, lastPos[c] 1)再用lastPos.count(c)来避免访问不存在的键。两种都可但第二种必须配合默认值 0 才能工作如果lastPos里没有c且默认返回 0则max(left, 1)可能会错误地把left提到 1所以我还是推荐上面的判断写法逻辑更直白。ans的更新放在每次循环末尾因为此时[left, right]一定是一个合法的无重复窗口用当前窗口长度去和答案比一比就好。3.2 哈希表更新的顺序不能随意调换有个细节值得单独说lastPos[c] right这行必须在计算ans之前执行而且要在更新left之后执行。如果先更新lastPos[c] right再算left那么lastPos[c]反映的就不是“上一次出现的位置”而是“当前这次的位置”冲突判断就失效了整个代码会认为是第一次见到这个字符。还有一个小众写法用mapchar, int而不是unordered_map。在 C 里map是红黑树查找 O(log n)虽然这个题目数据量下通常也能过但没必要。unordered_map平均 O(1)优先选它。但是unordered_map有一个隐藏问题后面细说。3.3 用数组替代哈希表性能差距能到几十倍绝大多数情况下题目的输入字符串只包含 ASCII 字符也就是最多 128 种可能。这种前提下完全不需要哈希表用普通数组就行下标直接当字符用class Solution { public: int lengthOfLongestSubstring(string s) { int lastPos[128]; fill(lastPos, lastPos 128, -1); int left 0; int ans 0; for (int right 0; right s.size(); right) { char c s[right]; left max(left, lastPos[(unsigned char)c] 1); lastPos[(unsigned char)c] right; ans max(ans, right - left 1); } return ans; } };这个版本有几个坑要注意。第一初始化值必须是-1这样lastPos[(unsigned char)c] 1就是 0不会干扰left也不需要判断字符是否出现过。第二char在 C 标准里是有符号还是无符号是implementation-defined有些编译器默认char是有符号的如果字符串里出现 ASCII 码大于 127 的字符直接拿它做下标会变成负数数组越界。稳妥做法是强制转成unsigned char保险起见数组开成128或者256都行我习惯写成256省心。实际跑性能测试的时候这个版本和unordered_map版本差距非常明显。我拿一个 100 万字符的随机串做对比纯属本地验证不同机器结果会有差异但数组版一般只需要几毫秒到十几毫秒unordered_map版可能需要上百毫秒原因很简单unordered_map每次插入或查找要算哈希、做桶定位还可能触发扩容和 rehash而数组就是一次随机访问。字符集固定且很小的时候别犹豫用数组。4. 调试实录与高频 Bug 复盘4.1 Bug 1left 回退输出莫名其妙变大这个 bug 我前面已经预告过了是这道题最典型的一个。症状是用abba或abcba这类“字符在窗口外但历史出现过”的用例结果比正确答案大 1 或者更大。根因就是更新left时没有做max保护直接拿lastPos[c] 1赋值。当你处理后面那个a时lastPos[a]还是位置 0但窗口左边界早就跑到 2 了直接覆盖就成了 1窗口一下子变大里面混进了重复字符。排查方法先跑几个小用例abcabcbb、bbbbb、pwwkew如果前两个都对第三个pwwkew结果变成 4正确答案是 3那八成就是left回退问题。再不行就在循环里打印left、right、当前字符、lastPos[c]观察left有没有变小。修法只有一个保证left严格单调不减。4.2 Bug 2窗口左移时忘了同步哈希表如果你用的是“窗口内字符集合”的写法最常见的问题是left往前移动一格删掉了一个字符但是集合里的记录没删导致后面判断重复时永远认为字符还在窗口内。这个 bug 的症状和上一个正好相反结果是输出偏小因为窗口被错误地限制住了。这类写法的修复要点是当且仅当left右移时同步从集合中移除s[left]对应的记录。但既然我们已经用“记录最后出现位置”的跳跃式写法了就完全不用担心这个问题。这也是我更推荐跳跃式写法的原因状态少一个bug 就少一截。4.3 边界条件速查表我把这道题最容易出问题的边界情况整理成一个表每次写完代码拿这几个例子跑一遍基本能暴露所有实现问题输入期望输出备注空串0注意循环直接不执行ans初始为 0单字符a1别把初始ans设置成奇怪的值全重复aaaa1验证窗口收缩逻辑全不同abcde5验证窗口扩张逻辑冲突在窗口外abba2验证max防回退经典用例abcabcbb3面试标准题pwwkew3出现字符w的连续冲突特别注意abba和abcba。abcba最长无重复子串是abc或cba长度 3这个用例对left回退检测特别敏感因为最后的a和开头的a重复但中间已经出现过b的冲突left已经滑到中间了。4.4 一个容易引起争论的细节哈希表存的是“位置”还是“计数”编码时有人会把lastPos存成字符出现的次数每遇到一个字符就加一然后在收缩窗口时把左边字符的计数减一直到所有计数都小于等于 1。这种“计数法”用在“最多 K 个不同字符”变体里是必须的但原题用“位置法”更优。原因是原题窗口的合法性只要求字符不重复重复字符出现时我们可以精确知道它上次在哪直接跳到那个位置后面而计数法必须一个字符一个字符地往外挪虽然复杂度也是 O(n)但常数更大。如果一个面试官看到你写位置法通常会追问一句“如果允许最多出现 K 次重复呢”这就引到下一章的变体了。5. 从这一题延伸出去的滑动窗口题单5.1 变体一最多 K 个不同字符的最长子串这是原题最常见的变体也是我推荐刷完原题以后马上练的一道给定一个字符串找最长子串要求里面最多包含 K 个不同字符。原题其实就是 K字符串长度因为窗口内不能有重复字符等价于所有字符出现次数不超过 1也等价于一种特殊的 K。这种题目就必须用“计数法”了因为窗口的合法性判断不再依赖“某个字符的唯一位置”而是依赖“窗口内不同字符的数量”。模板长这样int lengthOfLongestSubstringKDistinct(string s, int k) { unordered_mapchar, int count; int left 0, ans 0; for (int right 0; right s.size(); right) { count[s[right]]; while (count.size() k) { if (--count[s[left]] 0) { count.erase(s[left]); } left; } ans max(ans, right - left 1); } return ans; }注意这里left的移动用的是while而不是直接跳原因在于“不同字符数量超了”这个条件不能直接定位到该删哪个字符只能慢慢挪。对比原题的“跳跃式收缩”你会更直观地理解为什么原题能用位置法高效处理因为它的冲突信息是精确的而变体里的约束是统计性的二者本质不同。5.2 变体二最小覆盖子串另一类经典题是“找最短子串包含目标字符串中的所有字符”典型代表是最小覆盖子串。它同样用滑动窗口但窗口维护的目标从“最长”变成了“最短”所以收缩时机变成了“当窗口已经覆盖所有目标字符时尝试收缩直到不再覆盖”再记录最小值。这类题的核心是维护一个need计数器记录目标字符还缺几个。和原题对比原题窗口合法性是“内部无重复”覆盖类问题合法性是“内部包含了全部目标字符”完全相反但框架一模一样。所以我一直建议把这几道题放在一起刷无重复字符的最长子串、最多 K 个不同字符、最小覆盖子串、字符串排列。四道题刷完滑动窗口这个技术就基本刻进肌肉记忆了。5.3 面试官追问的几种方向理解原题之后面试官一般会沿着这几个方向继续挖如果输入是数据流也就是right不能回退、不能二次读取怎么处理其实滑动窗口本来就是单趟扫描天然适合流式输入。你只需要维护lastPos每来一个字符就按规则更新left和ans。这倒是原题的一个天然优势。如果字符集巨大比如全 Unicode怎么办数组方案就废了得回到unordered_map或者用更高阶的字典树方案但面试基本不会要求到那一步。如果字符串特别长内存放不下怎么办这属于外部算法题通常切开分块处理块与块之间需要小心处理边界上跨块的重复字符复杂度一下就上去了不是原题能覆盖的范围。我自己刷这道题的时候第一次是用“窗口内集合 逐格收缩”写出来的代码能过但也只是能过。后来被一个同事点了一句“你为什么不直接记住每个字符上次出现的位置”我才意识到位置法的妙处。从那个版本开始这道题在我手里就变成 5 分钟默写级别的题了。现在每次带人刷题我都会建议先理解窗口为什么不需要回退再亲手踩一次left回退的坑然后把位置法背下来。这个过程走完滑动窗口这关就算彻底过了。