★ FEATURED ARTICLE 第一次在刷题平台上看到“求字符串中不重复的最长子串的长度”这道 C 题时我的第一反应跟很多人一样这不就是枚举所有子串、再逐个检查有没有重复字符吗两层循环就能解决的事怎么会成为经典面试题。后来真正提交才发现暴力枚举在数据规模稍微大一点的时候完全没法看而背后的滑动窗口思想才是这道题真正的考点。这道题在 LeetCode有人习惯拼成 leecode上题号非常靠前几乎每个人的必刷清单里都有它。这篇内容就从最笨的枚举写法讲起一路走到 O(n) 的双指针标准解把每一步的原理、踩坑和经典用例都拆开来讲。不管你是刚准备刷题的新手还是已经刷了不少题但偶尔在边界条件上翻车的老手相信都能从里面找到点有用东西。1. 这道题真正考你的不是“最长”是“滑动窗口”1.1 为什么暴力枚举在数据规模稍大时必死先看最直觉的做法枚举每个起点 i再枚举每个终点 j得到子串 s[i..j]用一个标记数组或集合判断它是否包含重复字符没有重复就更新答案。如果字符串长度为 n子串总数是 n(n1)/2每个子串判重需要再扫一遍复杂度就是 O(n^3)。列个数量级感受一下n 为 100 时大约 50 万次字符检查毫秒级n 为 1000 时大约 5 亿次肉眼可见地卡顿n 达到 10^4 时5 x 10^11 次操作基本不可运行。而这类题目的真实测试数据动辄 10^5、10^6暴力版本连边都摸不到。有的读者会说我可以把判重过程优化成 O(1)固定起点 i逐步扩展终点 j同时维护一个布尔标记数组一发现重复就换下一个起点。这确实把整体复杂度降到 O(n^2)但 n10^5 时 10^10 次操作照样超时。问题的关键其实不是“判重够不够快”而是“有没有必要枚举所有可能的起点”。这就是为什么需要换个思路。1.2 子串还是子序列先分清楚再动手动手写之前有必要分清两个概念子串是连续的一段比如 abcabcbb 里的 abc、bca、cbb子序列不要求连续可以跳着取比如保持顺序挑出 aabb。题目问的是不重复的“最长子串”窗口模型天然匹配因为窗口就是一个连续区间。如果题目问的是子序列那解法完全是另一套通常要上动态规划千万别混为一谈。1.3 窗口的不变量才是代码的“根”滑动窗口做法的核心观察是当右端点 right 固定时左端点 left 只要移动到“窗口内恰好无重复”的合适位置这个窗口的长度就是当前 right 对应的最优值。并且 right 右移时left 只可能随之右移绝不会回退。两个指针都单调递增整段字符串一共只扫两遍。我写这类窗口时会在代码注释里强迫自己写清楚一条不变量在每一步循环结束后窗口 [left, right] 内的所有字符两两不同。后续所有边界判断都围绕这条不变量展开什么时候动 left、left 动到哪都要拿它验证。2. 滑动窗口的直觉右指针往前冲左指针负责清场2.1 手推“abcabcbb”的完整窗口移动过程拿最常见的用例 abcabcbb 完整推一遍。right0字符 a窗口内没有它left 不动窗口 [0,0]长度 1。right1b无重复窗口 [0,1]长度 2。right2c无重复窗口 [0,2]长度 3。right3又遇到 a而 a 上次出现在下标 0仍在我们窗口里于是 left 跳到 1窗口变为 [1,3]内容是 bca长度 3。right4又遇到 b上次出现在 1left 跳到 2窗口 [2,4] cab长度 3。right5c 上次出现在 2left 跳到 3窗口 [3,5] abc长度 3。right6b 上次出现在 4left 跳到 5窗口 [5,6] cb长度 2。right7b 上次出现在 6left 跳到 7窗口 [7,7] b长度 1。全程答案始终是 3。注意看 right6、7 时窗口长度反而变小了这是因为前面已经存在的重复字符限制了合法区间右指针再往右扫时窗口不可能回到 3 以上直到把左边那些旧字符彻底甩在窗外。2.2 上次出现位置表维护窗口的核心数据结构无论用 std::unordered_map 还是定长数组我们要维护的核心信息都是每个字符最近一次出现时的下标。当 right 扫到字符 c 时如果表里记录的 lastPos(c) 还在当前窗口内也就是 lastPos(c) left说明窗口里已经有一个相同的 c 了窗口不能再继续无脑扩张必须把 left 推进到 lastPos(c)1相当于把旧的 c 清出窗口。这里有一个未来会反复踩的细节为什么不是“只要表里有记录”就更新 left看到第 4 章就明白了很多错误代码都是栽在这一点上。2.3 哈希表还是定长数组选型的逻辑两种常见写法直觉完全一致unordered_mapchar,int 适合字符集不确定或 Unicode 输入通用但哈希有额外开销vector (128, -1) 适合纯 ASCII 输入直接索引速度快。如果题目限定只含小写字母int last[26] 也行但原题的数据并不只是小写字母直接写死 26 容易踩坑。我日常默认用 vector (128, -1)下标用 unsigned char 转换既快又不容易出错。3. 从暴力版到标准答案三个版本递进实现3.1 版本一枚举全部子串O(n^3)class Solution { public: bool allUnique(const string s, int start, int end) { bool seen[128] {}; for (int i start; i end; i) { unsigned char c s[i]; if (seen[c]) return false; seen[c] true; } return true; } int lengthOfLongestSubstring(string s) { int n (int)s.size(); int ans 0; for (int i 0; i n; i) { for (int j i; j n; j) { if (allUnique(s, i, j)) { ans max(ans, j - i 1); } } } return ans; } };这段代码的好处是正确性一目了然作为对拍工具很合适坏处是 n 稍大就超时。外层枚举起点 O(n)内层枚举终点 O(n)每个子串判重又是 O(n)合计 O(n^3)。哪怕优化掉一层只要还停留在“枚举所有起点”的思路上整体复杂度就压不下来。3.2 版本二set 双指针能过但常数大另一种自然想法用 set 维护窗口里的字符right 每遇到一个新字符如果 set 里已有它就一步步把 s[left] 删掉、left 右移直到没有重复再插入并更新答案。class Solution { public: int lengthOfLongestSubstring(string s) { unordered_setchar window; int left 0, ans 0; for (int right 0; right (int)s.size(); right) { while (window.count(s[right])) { window.erase(s[left]); left; } window.insert(s[right]); ans max(ans, right - left 1); } return ans; } };这个写法逻辑最简单也最容易讲清楚。整体均摊复杂度是 O(n)因为每个字符最多进 set 一次、出 set 一次。但注意内部有个浪费假设当前窗口很长而右指针遇到的重复字符恰好是最左边那个while 要连续删除大量元素才能把窗口收拾干净。虽然均摊线性实际常数比标准写法大不少。3.3 版本三位置表 左指针跳跃标准写法再进一步left 不需要一步一步挪直接跳到重复字符上次出现位置的下一个下标。中间那些字符虽然在历史记录里还有信息但已经不在新的窗口内不影响正确性。class Solution { public: int lengthOfLongestSubstring(string s) { vectorint last(128, -1); int left 0; int ans 0; for (int right 0; right (int)s.size(); right) { unsigned char c s[right]; if (last[c] left) { left last[c] 1; } last[c] right; ans max(ans, right - left 1); } return ans; } };每一步操作是 O(1)整体 O(n)。如果输入可能包含扩展 ASCII把 128 换成 256如果输入是不确定的 Unicode 字符集就把 vector 换成 unordered_map逻辑不变。这里把 char 转成 unsigned char 是为了防“负数字符下标越界”后文会专门说。3.4 三个版本怎么选版本时间复杂度空间复杂度特点枚举 判重O(n^3)O(1)正确性直观只适合小数据对拍set 双指针O(n) 均摊O(字符集大小)逻辑简单常数较大位置表 跳跃O(n)O(字符集大小)标准最优解面试首选如果你只是本地验证自己的思路版本一没有任何问题但如果要在评测平台上提交建议直接写版本三。4. 最容易翻车的一个角落left 更新为什么必须判断“旧位置还在窗口内”4.1 用“abba”复现一个隐蔽的错误写法好多人在从 set 版本过渡到位置表版本时会写出下面这种看起来“没问题”的代码// 错误示例缺少 lastPos[c] left 判断 unordered_mapchar, int lastPos; int left 0, ans 0; for (int right 0; right (int)s.size(); right) { char c s[right]; if (lastPos.count(c)) { left lastPos[c] 1; } lastPos[c] right; ans max(ans, right - left 1); }拿 abba 走一遍right0字符 a没有记录last[a]0窗口 [0,0]ans1。right1字符 b没有记录last[b]1窗口 [0,1]ans2。right2字符 b有记录 last[b]1left2窗口 [2,2]ans2。right3字符 a有记录 last[a]0left1窗口变成 [1,3]内容是 bba明显含重复字符 b可代码却会把 ans 更新成 3。问题出在 last[a]0 确实存在但 a 已经不在当前窗口 [2,2] 里了。盲目把 left 拉回 1等于把已经被甩到窗口外的旧字符又重新拉回来左指针回退不变量就崩了。正确做法是判断 lastPos[c] 是否仍大于等于 left只有上次出现的位置还在当前窗口内时才需要更新 left。4.2 正确的跳跃逻辑与哨兵值设计在 vector 版本里把 last 初始化成全 -1本质是用哨兵值统一处理两种情形从未出现过、以及出现过但位置在窗口外。因为 left 初始是 0-1 永远小于它不会触发跳跃同理那些过期的历史位置必然小于当前 left也会被跳过。这个设计让代码少了嵌套判断只要一行条件正确性就好验证。提示位置表版本把“某个字符之前出现过但位置已经不在窗口内”和“从未出现过”看成同一种状态处理这是它能用一行判断维护窗口干净的本质原因。4.3 答案更新时机别放在分支里还有一个细节我见过有人只在 left 变化时才更新 ans其余时候跳过。这是错的。随着 right 每一步移动窗口长度都在变化就算这次没有发生 left 跳跃新的窗口长度也可能刷新答案尤其当上一次 right 对应的窗口因为跳跃而缩水之后下一次扩展又可能回到更优长度。最省心的做法就是把 ans max(ans, right - left 1) 放在每轮循环末尾无条件执行。这条经验让我少踩过很多次“求最长合法窗口”类题目的坑。5. 边界用例、字符集坑和一次本地实测5.1 每次改完代码先跑的一组边界用例我整理了一张固定清单改完滑窗代码会先逐个测一遍输入预期输出说明0空串无子串 1空格也是有效字符a1单字符aaaaaa1所有子串都含重复abcd4整个串无重复abba2专门测 left 是否会回退abcabcbb3最经典用例pwwkew3pwke 不连续正确结果是 wke 或 kew其中 abba 是我最看重的一条。因为它几乎能命中所有“left 更新缺少边界判断”的错误写法跑一次就原形毕露。5.2 ASCII、扩展 ASCII 和 char 符号的坑C 里 char 是否带符号依赖编译器。字符串中如果出现编码值大于 127 的原始字节直接取 s[right] 可能得到负数拿负数去索引 vector 会越界轻则 dirty read重则直接运行错误。稳妥做法是把 char 转成 unsigned char 再索引或者把数组开成 256。原题字符范围就是标准 ASCII所以 128 足够但如果想兼容扩展 ASCII 或误传中文编码的字节建议直接 256代价可以忽略。5.3 本地实测一轮 unordered_map 与 vector我在本地随机生成 10 万位由大小写字母和数字组成的字符串把两个版本各跑多次取大致耗时。结果很稳定vector (128, -1) 版本大概比 unordered_mapchar,int 版本快三四倍。原因不难理解数组索引是一次内存访问unordered_map 要算哈希、处理桶冲突。真实面试场景中输入通常只是 ASCII优先选数组如果输入可能包含任意 Unicode 码点再换 unordered_map那时候性能差距反而不是第一优先级。注意具体倍数受编译器和机器影响不代表权威 benchmark但性能趋势是稳定的。5.4 中文等多字节字符串怎么办如果输入是中文或其他 Unicode 字符直接按 char 遍历会把一个字符拆成多个字节。比如一个汉字在 UTF-8 下占 3 字节两个相同汉字会被当成 6 个“字节级字符”处理判重逻辑完全错位。处理思路是先把字符串解码成 Unicode code point 数组再跑同一个滑动窗口或者使用支持 Unicode 的宽字符方案。这道题的标准数据用不到这个扩展但实际业务里经常碰到值得知道有这么回事。6. 把滑动窗口这套思维搬到隔壁题型6.1 同样骨架的经典变体学完这道题能顺带迁移的几个题型求最多包含 k 个不同字符的最长子串窗口合法性从“无重复”变成“不同字符数 k”维护计数表而不是位置表。求最长无重复子数组元素从字符变成整数换 unordered_mapint,int 就能直接照搬同一套逻辑。字符串替换后的最长重复字符条件变成“可替换次数最多 k”窗口合法性变成“窗口长度 - 窗口内最多字符数 k”本质上还是同一副骨架。这些题目在面试里出现频率不低模板熟了之后基本是换条件、换数据结构。6.2 面试时怎样展示思路递进如果是在面试现场写这题我会按三个步骤讲先摆暴力 O(n^3)指出它重复枚举了大量必然包含重复字符的子串浪费明显。提出双指针 set把“窗口内保持无重复”作为不变量先拿到可运行的线性做法。再优化为位置表 跳跃式左移解释为什么能跳过中间删除操作以及 left 为什么不可能回退。三层递进本身就是一套很好的沟通脚本。面试官要的不一定是直接写出最优解而是看到你有复杂度和正确性的自检意识。6.3 我总结的滑窗三问模板后来我遇到任何滑动窗口题都会先回答三个问题再动手窗口内的信息用什么结构维护什么时候需要移动左指针移动到哪个位置什么时候更新答案。对应到本题分别是位置表遇到重复字符且旧位置仍在窗口内时跳到旧位置加 1right 每步移动后都更新。其他滑窗题只是把答案换成“最多 k 个不同字符”“可替换次数等于 0”之类的条件骨架不变。我最初刷这题时其实是先 AC 了 set 版本但真正理解“跳跃式左移”是在被 abba 这类输入连续打脸之后。现在回看滑动窗口的难点从来不是代码本身而是你能不能构造出反例去验证自己的逻辑。如果你也想彻底拿下它建议在本地把三个版本都写一遍再把我上面那张边界用例表逐行跑过。一次跑明白后面再遇到这题的变体就会轻松很多。
阅读完成 · 觉得有帮助？
