1. 今日题目与选题理由今天是坚持每日算法题的第5天这个习惯算是慢慢熬过最难受的适应期了。前四天我分别练过数组遍历、链表翻转、哈希计数和双指针都是基础中的基础。今天特意挑了一道字符串领域的高频题——无重复字符的最长子串作为这个系列第5篇的主角。这道题我推荐给每个刚开始刷题的人原因有三个题意清晰不绕、解法有典型梯度、面试变形空间大。很多公司在笔试筛选环节都会把这题当热身题因为它能同时考察候选人对“区间维护”的直觉、对哈希结构的敏感度以及代码边界处理是否细致。题目本身不难理解但只要往深里问可以一直问到字符串匹配、字符集扩展乃至滚动哈希属于典型的“小题目大文章”。具体题目是这样的给定一个字符串 s请你找出其中不含有重复字符的最长子串的长度。比如 s abcabcbb不含重复字符的最长子串是 abc长度是 3s bbbbb答案自然是 1s pwwkew最长子串是 wke 或者 kew长度是 3。我之前经常看到有同学在评论区说这题不是很简单吗两层循环枚举一下不就行了。确实暴力枚举能解出来但在真正的笔试环境里基本拿不到满分因为数据规模一大性能差距就体现出来了。这篇文章我会从暴力解法讲起一步步还原我是怎么想到滑动窗口的然后把写代码时踩过的坑、边界条件的处理、调试过程中的细节都摊开讲。不管你是刚开始接触算法题的新手还是准备系统性复习的老手这篇应该都有你能用上的东西。2. 题目拆解与两个高频误区2.1 审题先审清楚子串不是子序列先说第一层理解。题目要求的是“子串”不是“子序列”。这两个概念太容易混淆了。子串要求从原字符串中连续截取一段比如 abcabcbb 里的 bca 就是一个子串而子序列只要求保持相对顺序字符之间可以跳着选比如 abcabcbb 里的 acb 也可以是子序列但它不是连续出现的。为什么这个区分很重要因为连续性强意味着我们可以用区间工具去维护它而不需要做组合枚举。如果题目问的是子序列那解法方向就完全变了大概率会走向动态规划。所以第一步不是急着写代码而是确认题目到底在问哪种结构一旦审题错误后面全盘皆输。题目还有一个关键词是“不含有重复字符”等价说法是子串内部任意两个位置的字符都不同。这个约束决定了我们需要一种快速判断“当前区间是否有重复字符”的手段哈希集合HashSet自然就成了第一选择。2.2 误区一暴力枚举所有子串并判断去重很多人的第一反应是枚举所有子串对每个子串再判断内部是否有重复字符。这个思路完全正确但复杂度失控了。字符串长度为 n 时子串数量大约有 n(n1)/2 个如果你对每个子串都重新扫描一遍判断是否无重复最坏情况会达到 O(n^3) 的复杂度。举个更具体的例子如果 n 是 10 万这个计算量在普通机器上基本跑不完。在实际机试中这个复杂度意味着你可能连部分测试样例都过不了。我见过一个同学在面试现场写出这种暴力解法面试官没有直接否定而是问了一句“假设字符串长度是 100000你这个程序需要运行多久”这个问题的目的就是引导你分析复杂度而不是单纯让你背答案。2.3 误区二遇到重复就把窗口重置还有一种思路比纯暴力好一点但依然是错的用一个左指针从左往右扫每次遇到重复字符就把左指针加 1但右指针不回溯。这种写法在一些用例上会漏解。举个例子s abca。当你扫描到索引 3 的字符 a 时发现它和索引 0 的 a 重复了如果只是把左指针从 0 移动到 1那么你的窗口会变成 bca长度是 3这刚好还是对的。但如果换成 s abcdaef从索引 0 的 a 和索引 4 的 a 重复你把左指针移到 1窗口变成 bcdaef仍然没有重复长度 6又碰巧对了。真正的问题出在更复杂的场景当重复字符不在当前窗口的最左端时只把左指针加 1 会保留重复字符在窗口内导致冲突依然存在。比如 s abac左指针从 0 开始扫到索引 2 的 a 时发现和索引 0 重复你把左指针移到 1窗口变成 ba没有重复似乎又没事。但换个例子 s abcac扫到索引 3 的 a 时左指针移到 1窗口变成 bca 加上新的 c不这里需要仔细推演总之核心问题是左指针必须跳转到“重复字符上一次出现位置的下一个位置”而且如果上一次出现的位置已经在左指针之前则不能往回跳。很多初学滑动窗口的人都在这里栽过跟头。处理逻辑其实非常明确当发现 s[right] 与窗口内某个字符重复时应该把 left 直接移动到 max(left, last_pos[s[right]] 1)而不能简单地 left。这里用 max 是防止字符上一次出现位置已经在 left 左边那种情况说明该字符的“旧副本”早就被排除在窗口之外了不需要响应。3. 解法演进从暴力到滑动窗口3.1 暴力解法当跳板在给出最优解之前我习惯先写出一个能跑通的暴力版本不是为了提交而是为了确保自己对题意的理解没有偏差。暴力思路非常简单枚举每一个左端点 i然后从 i 开始不断向右延伸用一个集合记录已经见过的字符。每次延伸一个字符先检查它是否在集合里如果在就停止这一轮记录当前长度如果不在就加入集合并更新答案。用 Python 写出来大概是这样def length_of_longest_substring(s: str) - int: n len(s) ans 0 for i in range(n): seen set() for j in range(i, n): if s[j] in seen: break seen.add(s[j]) ans max(ans, j - i 1) return ans这个代码逻辑没有错但性能很差。分析复杂度时要注意外层循环 n 次内层循环最坏也是 n 次整体 O(n^2)。不过你注意没有代码里其实藏着一个重要信息——当内层循环因为遇到重复字符而停止时我们已经知道了从 i 到 j-1 这一段是无重复的。这个信息在下一次外层循环里会直接被浪费掉而滑动窗口恰恰就是利用这个信息的。3.2 滑动窗口的核心思想暴力解法的问题在于重复检查。假设在某一轮里我们已经验证过区间 [i, j) 是无重复的而且右指针碰到的一个字符 s[j] 和区间里的 s[k] 重复了。下一轮把 i 加 1 之后区间 [i1, j) 明明上一轮已经验证过无重复了暴力解法却还要从头再检查一遍这种重复劳动完全没有必要。滑动窗口的思路是维护一个永远不会包含重复字符的区间 [left, right)。右指针 right 负责扩展窗口每加入一个新字符就检查它是否和窗口内已有字符冲突。如果冲突就让左指针 left 不断向右移动同时把离开窗口的字符从集合里移除直到冲突解除。然后继续扩展右指针。你可以把窗口想象成一条传送带上可以伸缩的夹子夹子永远夹住一段没有重复字符的区间。新字符送到夹子右端时如果区间内已经有同样字符了夹子左端就自动向右推直到整个区间恢复无重复状态。用这种方法每个字符最多被 left 和 right 各碰触一次整体复杂度是 O(n)。这和暴力解法最本质的区别是暴力解法把已经验证过的区间当成没经验滑动窗口把每一次查验的结果都保留下来左指针的移动是智能跳跃而不是机械重试。3.3 维护窗口的数据结构选择实现滑动窗口最自然的数据结构是无序集合 unordered_set / HashSet。它的作用只有一个判断当前窗口内是否存在某个字符。但这里有一个进阶问题如果只用一个集合当我们发现冲突时只能知道“存在重复”却不知道重复字符上一次出现在窗口内的哪个具体位置。所以普遍采用两种策略第一种是配合 while 循环不断收缩左边界直到窗口内没有重复字符。这种方式实现简单代码短每个字符最多进出窗口各一次仍然保持 O(n) 复杂度。在很多在线评测平台上这个版本已经足够快了。第二种是用一个哈希表记录每个字符最近一次出现的下标。当发现重复时直接把左指针跳到重复字符上一次出现下标加 1 的位置这样可以省掉 while 循环里的逐步收缩。但要注意如果字符上一次出现的位置已经在左指针左边就不能让左指针回退所以左指针的更新公式要写成 left max(left, last_pos[c] 1)。两种方式在复杂度上是同一个量级第一种更适合写进面试的白板代码第二种在字符集比较大的场景下常数更优。我个人建议先把第一种吃透因为它更贴近滑动窗口的原始定义后续遇到别的问题也好迁移。4. 多语言代码实现与关键细节4.1 C 实现双指针与哈希集合下面是我实际提交过的一版 C 代码class Solution { public: int lengthOfLongestSubstring(string s) { unordered_setchar window; int n s.size(); int left 0, ans 0; for (int right 0; right n; right) { while (window.count(s[right])) { window.erase(s[left]); left; } window.insert(s[right]); ans max(ans, right - left 1); } return ans; } };代码里最值得琢磨的是 while 循环的语义。当 s[right] 和窗口内某个字符重复时我们不是直接删除 s[right]而是删除窗口最左端的 s[left]然后 left 加 1。这一步的逻辑是窗口区间是连续的要把一个内部的重复字符赶出去必须先把这个字符左侧的所有字符都移出窗口。比如窗口是 [left..right-1]重复字符在位置 p那么只有把 left 推进到 p1窗口才能重新变干净。while 循环就是负责完成这个“赶出窗口”的过程它删掉的是一个一个的左边界字符而不是那个被检测到的重复字符。这里有一个很容易写错的变种有人会在 while 里写 window.erase(s[right])这就是把因果关系搞反了。s[right] 还没加进窗口删它没有任何意义此时需要的是调整 left。4.2 Python 实现与切片的陷阱Python 版本的代码可以很简洁def length_of_longest_substring(s: str) - int: window set() left 0 ans 0 for right, ch in enumerate(s): while ch in window: window.remove(s[left]) left 1 window.add(ch) ans max(ans, right - left 1) return ansPython 用 for right, ch in enumerate(s) 比较方便right 天然就是下标。这个版本里最容易踩的坑是 window.remove(s[left]) 和 window.remove(ch) 的混淆。必须记住我们的目标是让窗口不断收缩直到 ch 不再出现在窗口里所以移除的始终是左边界字符这和 C 版本的逻辑是一致的。另外注意Python 的 set 是无序的但这里我们只关心“有没有重复”和“移除最左边字符”并不依赖 set 的顺序所以用 set 完全没问题。4.3 更进一步的哈希表版本如果想在字符重复时一步到位跳转左指针可以用哈希表记录字符最近出现的位置。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这个版本的精髓在 if 判断只有当字符已经出现过且上一次的出现位置不早于当前左指针时才更新 left。为什么要加 last_pos[ch] left 这个条件因为 left 一直在向右移动某个字符可能在 left 之前出现过很多次但那些位置已经不在窗口范围内了此时不应当用旧位置来收缩窗口。这个细节特别容易忽略一旦漏掉这个条件代码在特定用例下会产生错误结果。用这个版本重新看 s abba 的例子right2 遇到第二个 b 时last_pos[b]1left 更新为 2right3 遇到 a 时last_pos[a]0但 0 left所以 left 不更新最终答案正确。这就是 max 判断的必要性。5. 复杂度分析与一段性能实测5.1 时间复杂度到底怎么算先从暴力解说起。暴力解法外层循环最多 n 次内层循环又最多 n 次所以 O(n^2)。如果内层每个字符都要在集合里做一次哈希查找常数还要更大一点。而滑动窗口版本我们来仔细数一数。right 指针从 0 到 n-1 一共前进了 n 次这个没有疑问。关键是 left 指针它会不会在某些情况下反复移动不会。left 永远只向右移动而且每次移动都会从窗口中删除一个字符这个字符一旦被删除就再也不会被加进来除非将来 right 再次经过它不right 只会向右不会回头所以每个字符至多被 left 删除一次。因此整个算法中每个字符最多被 right 访问一次被 left 访问一次总操作次数是 2n 量级时间复杂度 O(n)。这个分析思路你一定要掌握因为几乎所有双指针类题目的复杂度分析都是同样的套路两个指针都只向一个方向移动总移动次数被限制在线性范围内。5.2 空间复杂度与字符集的关系滑动窗口版本的空间复杂度是 O(min(n, 字符集大小))。这个“字符集大小”是什么因为窗口内不可能存储超过字符集总数量的不同字符。如果题目只包含英文字母那窗口内最多 26 个不同字符如果包含 ASCII 全部字符那就是 128如果包含 Unicode 全量字符那么窗口内理论上限会很大但实际上受限于字符串长度 n。所以在做这一类题的时候先问清楚输入字符集是什么。如果是 26 个字母可以用长度为 26 的数组代替哈希集合常数开销更小代码清晰度也会提升如果是任意 ASCII可以用长度 128 的数组。只有在字符集无法预先确定的场景才应该使用哈希集合。我实际测过长度为一千万级别的随机字符串滑动窗口版本运行时间大约是几百毫秒到一秒多具体取决于字符集大小和字符串本身的重复程度。暴力解法在这个规模上跑了一个多小时也没跑完最后被我强制终止了。这个对比不需要多说你也能感受出 O(n) 和 O(n^2) 的差距。5.3 一道特殊用例带来的思考有一个很经典的边界输入是空字符串 s 。几乎所有实现都要回答这个问题ans 初始值是 0循环根本不会执行返回 0这没问题。还有一个输入是长度为 1 的字符串 s a。循环执行一次window.add(a)ans max(0, 01) 1返回 1也没问题。但如果你把 ans 的初始值设成 1空字符串就会回答出错所以初始值一定要斟酌好。更极端的一个情况是 s 由同一种字符重复组成比如 aaaaa。滑动窗口会不断重复“加入 a、发现重复、删除 a、再加入 a”的过程ans 始终是 1这个结果是正确的。但如果你用哈希表版本要注意 left 的更新逻辑每个 a 的 last_pos 都在更新left 也会一步一步地向右推进同样回答 1。我有一回在本地测试的时候故意用了一个包含各种生僻 Unicode 字符的字符串比如 emoji 和组合字符。Python 的字符串按 Unicode 码位遍历但某些组合字符由一个码位加多个修饰字符构成从视觉上看是“一个字符”遍历时却会被拆成多个。遇到这种输入题目本身定义的“字符”就需要和面试官确认清楚。真实的日常业务场景里这种边界很多人都会忽略。6. 常见错误、调试心得与刷题节奏建议6.1 我实际踩过的四个坑第一个坑是窗口收缩的条件写反了。有些版本代码会在循环里判断 s[right] not in window然后进入 while 收缩逻辑直接搞反。实际上只有当 s[right] 已存在于窗口时才需要收缩收缩的条件应该是存在性判断。第二个坑是忘记更新 left。哈希表版本尤其容易犯这个错误因为少写一行 left max(left, last_pos[s[right]] 1)在某些用例下依然能碰巧答对但在长字符串重复场景下就会漏解。这种错误非常隐蔽因为部分测试用例不会触发。第三个坑是自以为答案是子串本身而不是长度。有人花了大功夫在代码里保存最长子串的具体内容然后返回字符串最后的类型都对不上。我们在算法题里一定要先确认输出的类型这道题问的是 int不是 string。第四个坑是在 C 里把 unordered_set 写成 set。这个不一定会答错但 log n 的复杂度会让性能下降在大型用例上可能超时。做题时要注意数据结构的选择特定平台下 set 的有序性在这里没有用。6.2 一个有效的调试技巧调试滑动窗口问题时我推荐在循环里打印窗口状态。最直接的方法是输出 right、left、当前字符、窗口内容。以 abcabcbb 为例第一次出现重复是在 right3 的时候字符是 a此时窗口从 {a,b,c} 收缩到 {b,c}不对应该收缩到 {b,c} 之后加入 a窗口变成 {a,b,c}。你把调试信息打印出来之后会发现窗口的变化完全符合预期任何一步与预期不符都能快速地定位到代码里的逻辑错误。这个技巧看似基础但很多新手直接跳过埋头看代码找错效率很低。打印日志的时间成本远比瞎猜要低尤其是涉及双指针和区间维护的题目视觉化呈现窗口状态能极大降低心智负担。6.3 每日一题的整体节奏怎么安排既然今天已经进行到第 5 天那我顺便分享一点关于刷题节奏的体会。前几天的题目尽量选基础题型目标不是解出题而是把“读题、画样例、写暴力、分析复杂度、优化、再验证”这个完整流程走顺。很多人刷题贪多一天三四道每道题看一遍题解就过一个星期后什么都记不住本质上是因为缺少了“亲手推导最优解”的过程。一道题如果当天没有想出来我一般会记录下来不急着看题解。先把暴力解法写出来再对着暴力解法的复杂度瓶颈思考哪里在做重复计算。这个“自己推导到卡住”的体验是有价值的因为当你之后再看到题解中巧妙的优化时那个“啊哈”时刻会帮助你记得特别牢。今天的这道无重复字符最长子串就是一个典型的推导链路暴力枚举 O(n^2)、发现重复验证是冗余、引入区间维护、再引入哈希表直接跳跃。等你把这个链路背熟了再遇到“替换后的最长重复字符”“字符串的排列”“最多 K 个不同字符的最长子串”这些变体你会看到它们都在同一个思想框架之下。6.4 面试中怎么讲这道题如果这道题出现在面试里我建议你按下面的顺序讲第一步先确认题意明确指出子串是连续的。第二步讲暴力解法用一句“最坏情况是 O(n^2)因为每个起点都要往后枚举”把复杂度点明。第三步自然过渡到滑动窗口重点解释为什么之前验证过的区间信息可以复用。第四步代码实现。第五步面试官如果不打断主动补充复杂度分析。在这个讲述过程中有一个非常加分的细节当你提到用哈希集合时主动说一句“这里的字符集大小会影响空间复杂度的上限”这能向面试官展示你对问题边界的思考。如果面试官追问扩展你可以接上“如果只有小写字母可以直接用数组替代哈希集合能把常数降得更低。”6.5 这个系列后续还能怎么延伸到第 5 天为止我已经练习了数组、链表、哈希、双指针和今天的滑动窗口。这些内容看似分散其实都在为后面更复杂的题型打底。接下来我准备把滑动窗口和前缀和结合起来练比如“长度最小的子数组”这类题目再往后窗口内维护的内容可能从字符变成数值的统计信息这就为处理“字符串中的好子串”等进阶题做好了准备。我个人每天刷题后都会花 10 分钟快速复盘今天这题的解法用到了什么思想和前天那道题的解法有没有相通之处如果题目加一个限制条件我要怎么调整。这种复盘习惯比多刷一道题重要得多也推荐你试试。