刷题刷到第7篇了进度条走到7/100。今天这篇是LeetCode Hot100里的第3题——无重复字符的最长子串。别小看这道题它是滑动窗口思想的入门代表作面试出镜率极高而且它背后那套“维护一个合法窗口”的思路后面很多中等题、难题都在用它。如果你刚开始刷Hot100这道题非常值得停下来好好吃透而不是背个答案就过去。我用实际刷题的过程把它讲透从暴力解法怎么想到滑动窗口到两版主流写法哈希集合版、哈希索引版各自的设计逻辑再到踩坑点和调试技巧。适合刚刷题不久的新手也适合想彻底搞懂边界细节的老手。1. 题目到底在问什么为什么暴力解法不够用1.1 先看懂题意是子串不是子序列题目要求很简单给定一个字符串s请你找出其中不含有重复字符的最长子串的长度。注意这里的关键词是“子串”不是“子序列”。子串要求字符在原字符串中是连续的比如pwwkew这个串wke是子串但pwke不是因为中间跳过了那个重复的w。子序列才允许跳着选。很多新手第一次做这道题就在这个语义上翻车了用子序列的思路去算结果怎么算都不对。再看几个官方示例s abcabcbb输出 3因为最长无重复子串是abc长度为 3。s bbbbb输出 1因为不管怎么切子串里都只有b最长就是单独一个b。s pwwkew输出 3最长是wke。s 输出 0空串没有子串。最后这个空串边界千万别漏题目如果没明说长度范围你也要自己想到。LeetCode 上这道题的字符串长度上限是5 * 10^4意味着 O(n²) 的解法在极端情况下会非常吃力所以我们必须往 O(n) 的方向去想。1.2 暴力解法的思考路径以及它到底慢在哪拿到这题第一反应肯定是枚举。枚举所有可能的子串对每个子串检查有没有重复字符然后取最大长度。枚举起点和终点是 O(n²)检查重复又要 O(n)整体就是 O(n³)。对于 n 最大 50000 的输入这个复杂度基本是跑不完的。稍微优化一步固定起点然后让终点往右扩展扩展的同时用一个哈希集合记录当前窗口里出现过的字符。每扩展一个新字符就检查它是否已经在集合里。这样一来检查重复的代价被摊到扩展过程里枚举复杂度降到了 O(n²)。比如对abcabcbb固定起点 0扩展a - ab - abc到第四个字符a时发现重复记录当前长度 3然后换起点 1 继续。但 O(n²) 还是太慢。瓶颈在哪里在于每次发现重复后我们只把答案记下来然后整体放弃当前窗口把起点往右挪一格重新开始扩展。这个过程里后一个起点能复用的信息几乎为零大量比较是重复劳动。我自己刷的时候会在纸上推abcabcbb推着推着就会发现一个现象当窗口是abc时下一个字符a和窗口里的a重复了但其实我们没必要从b重新开始因为bc一定比abc短我们想要的只是“不重复的、尽可能长的窗口”。如果能保留从b、c开始的那部分信息效率自然就上来了。这就是滑动窗口直觉的来源。1.3 滑动窗口的核心思想维护一个“永远合法”的窗口滑动窗口的思路是用左右两个指针left和right框出一个子串区间[left, right]并且让这个区间始终满足“无重复字符”这一条件。right负责向外扩张探索新的字符一旦发现新字符和窗口内的字符冲突就移动left把窗口左侧的重复字符赶出去直到窗口重新合法。这个思路的本质是我们不需要枚举所有子串只需要维护“以当前right为结尾的最长无重复子串”答案就是这些子串长度的最大值。因为任何最长无重复子串一定是某个位置作为右端点时窗口能覆盖的最远范围。这个道理可以类比成一条传送带right是传送带的末端不停把新货物放进来left是质检员发现传送带上有重复货物时就往前推把重复的那件连同前面的旧货一起清走。传送带始终保证没有重复我们记录传送带在运行过程中的最大长度。理论清楚了实现上有两条路线。一条是哈希集合版left缓慢移动遇到冲突就一步一步往右走直到重复字符被移除另一条是哈希索引版额外记录每个字符上一次出现的位置遇到冲突时直接把left跳到重复字符上次出现位置的下一个位置。后者代码更短但left的跳转规则里有不少细节后面我会重点讲。2. 两版主流写法的实现细节与代码解析2.1 哈希集合版直观、好写、容易理解哈希集合版的逻辑最贴近原始直觉。我们维护一个set里面存当前窗口内的所有字符。right从头走到尾每遇到一个新字符就检查它是否已经在集合里如果在就不断从集合里删除s[left]并把left右移直到冲突解除然后把这个新字符加进集合更新答案。def length_of_longest_substring(s: str) - int: n len(s) if n 0: return 0 window set() left 0 ans 0 for right in range(n): # 只要 s[right] 还在窗口里就移动左指针缩小窗口 while s[right] in window: window.remove(s[left]) left 1 # 此时窗口内一定没有 s[right]可以放心加入 window.add(s[right]) # 更新答案 ans max(ans, right - left 1) return ans简单梳理几个细节外层循环的right是“当前子串的右端点”每次循环结束时window中恰好是[left, right]这个区间内的字符。while循环可能执行 0 次、1 次或多次。最坏情况是right每走一步left都要跟着走一步比如输入abcde这种无重复串while一次都不执行而输入aaaaa这种全是重复字符的串每来一个新awhile都要删掉一个旧a。整体来看left在整个算法过程中最多移动 n 次所以总时间复杂度是 O(n) 而不是 O(n²)。每次更新答案用max(ans, right - left 1)因为right - left 1正好是当前窗口长度。我把abcabcbb的前几步手推一遍大家感受一下这个过程right当前字符leftwindow冲突处理ans0a0{a}无11b0{a,b}无22c0{a,b,c}无33a0{a,b,c}发现重复 a删除 s[0]aleft→134b1{b,c,a}无此时窗口为 bca35c1{b,c,a}无窗口为 bcabc 中 left 指向 b 后面3注意看 right3 这一步删除a后窗口变成{b,c}再添加新a变成{b,c,a}此时窗口实际上是s[1..3] bca是合法的。整个过程里窗口的最大长度一直是 3所以答案是 3。2.2 哈希索引版一次遍历就够但 left 跳转有讲究集合版虽然简单但while循环让left一个字符一个字符地挪。如果能在遇到重复时直接算出left该跳到哪效率还能再进一步。于是就有了哈希索引版用map记录每个字符最近一次出现的位置。遍历right时如果发现s[right]在map里说明这个字符之前出现过那么直接把left跳到map[s[right]] 1的位置即重复字符上次出现位置的后一个字符。这样就跳过了中间所有必然包含重复字符的子串。def length_of_longest_substring(s: str) - int: n len(s) if n 0: return 0 last_pos {} left 0 ans 0 for right in range(n): ch s[right] if ch in last_pos: # 窗口的 left 只能前进不能回退 left max(left, last_pos[ch] 1) # 记录或更新当前字符最近出现的位置 last_pos[ch] right # 更新答案 ans max(ans, right - left 1) return ans这里最容易被忽视的就是left max(left, last_pos[ch] 1)这个max保护。很多初学者写成left last_pos[ch] 1结果在处理abba时直接出错。我用abba推演一遍错误写法会发生什么right0chaleft0last_pos{a:0}ans1。right1chbleft0last_pos{a:0,b:1}ans2。right2chb发现 b 上次出现在 1left 1 1 2last_pos{a:0,b:2}ansmax(2, 2-21)2。right3cha发现 a 上次出现在 0此时如果直接写left 0 1 1窗口变成[1,3]对应bba里面有两个 b明显是错的。正确应该用max(2, 01) 2窗口[2,3]对应ba合法。这个问题本质上是当前left已经因为更靠后的重复字符移动到了位置 2而a上次出现的位置是 0这个信息已经“过期”了它不应该把left往回拉。窗口的左边界只能向右移动不能回退所以必须用max夹住。2.3 边界条件与每个写法的易错点刷这道题最容易出问题的地方集中在几个边界场景。第一空串处理。很多解法在开头直接写if not s: return 0这个一定不能省。虽然输入可能非空但谁也说不好测试用例里会不会混一个写了对后面的逻辑完全没有副作用。第二单字符和全重复串。a返回 1bbbb返回 1。集合版遇到全重复串时while循环每次都会执行一次删除最终答案从 1 开始一直不变哈希索引版则每次都会触发left跳转效果同样正确。第三字符集范围。LeetCode 这道题默认输入是 ASCII 字符但 Python 的字符串实际上是 Unicode 序列。如果面试官把题目扩展到包含中文的输入用哈希集合和哈希索引都没有问题因为哈希本身不依赖具体字符集。如果你用固定大小的数组做优化比如int[128]或int[256]就必须先确认字符集范围否则会越界或漏判。这道题用数组优化是可选的加分项但不建议为了炫技破坏通用性。第四Java 版注意charAt和字符串长度。在 Java 里写s.charAt(right)是 O(1) 操作但如果你频繁调用s.substring(left, right)来观察窗口内容复杂度就不是 O(1) 了因为substring在新版本 Java 里会复制字符数组。我见过有人为了调试方便在每个循环里substring一下结果整个算法被拖慢这是个大坑。下面是 Java 哈希索引版的参考实现public int lengthOfLongestSubstring(String s) { int n s.length(); if (n 0) { return 0; } MapCharacter, Integer lastPos new HashMap(); int left 0; int ans 0; for (int right 0; right n; right) { char c s.charAt(right); if (lastPos.containsKey(c)) { left Math.max(left, lastPos.get(c) 1); } lastPos.put(c, right); ans Math.max(ans, right - left 1); } return ans; }Java 版和 Python 版逻辑完全一致只是 API 更啰嗦一些。如果你想在 Java 里用数组优化可以把MapCharacter, Integer换成int[] pos new int[128]初始值全部置为 -1遇到字符时判断pos[c] ! -1。这个优化在面试中偶尔会被追问后面我会单独说。3. 进一步优化哈希索引法背后的复杂度与变体3.1 为什么哈希索引法通常更快但集合版也很好从大 O 复杂度看两版都是 O(n)。但从常数因子看哈希索引法通常更优因为它没有while子循环。集合版虽然left总共只移动 n 次但while循环的每次迭代都要执行一次集合删除操作和一次左指针加一哈希索引法把这些操作压缩成了一行left max(...)的跳转。不过“快”不是唯一的衡量标准。集合版的优势在于循环不变式非常直观每次循环结束时窗口一定合法。这个性质让它在遇到更复杂的变体题时更容易扩展。比如有些题目除了“无重复字符”还要求“不超过 K 个不同字符”这类题的直觉解就是集合版那个“遇到冲突移动左指针直到条件重新满足”的模板而不是哈希索引版的直接跳转。所以两版都值得熟练掌握面试时根据题目要求选型。3.2 时间复杂度和空间复杂度的严谨分析时间上哈希索引版只需一次遍历每次操作都是 O(1) 的哈希读写总复杂度 O(n)。集合版虽然内层有while但请记住一个重要性质left在整个过程中只增不减最多从 0 走到 n所以内层循环的总执行次数是 O(n)摊还下来整体仍是 O(n)。空间上两个版本都需要存储窗口内出现过的字符。这里贴一个容易忽略的细节空间复杂度严格说是 O(min(m, n))其中 m 是字符集大小n 是字符串长度。窗口不可能超过字符集大小因为超过必然出现重复窗口也不可能超过 n因为子串长度不可能超过整个字符串。所以用两个上限里较小的那个来刻画更准确。对于 ASCII 输入m 最多 128 或 256可以说是常数额外空间对于 Unicode 输入m 会大很多。如果你用数组int[128]优化哈希表空间复杂度就严格变成 O(1)因为数组大小固定不随输入规模变化。这是面试官喜欢追问的一个点。public int lengthOfLongestSubstring(String s) { int n s.length(); int[] pos new int[128]; Arrays.fill(pos, -1); int left 0; int ans 0; for (int right 0; right n; right) { char c s.charAt(right); // 这里做一次强转把字符变成数组下标 int idx c; if (pos[idx] ! -1) { left Math.max(left, pos[idx] 1); } pos[idx] right; ans Math.max(ans, right - left 1); } return ans; }数组版的要点是char可以当成整数下标使用128 覆盖了所有 ASCII 可打印字符。如果题目明确说是 ASCII这个写法最干净如果不确定字符集还是用哈希表更稳妥。3.3 从这道题延展开相关变体与后续刷题方向这道题是滑动窗口的母题掌握它之后很多题都能套同一个思考框架。先说变体。LeetCode 340 题“最多含有 K 个不同字符的最长子串”和 159 题“至多包含两个不同字符的最长子串”都是这道题的直接扩展。它们的区别从“不能有重复字符”变成“允许出现有限个不同字符”解法仍然是用左右指针维护窗口状态只不过冲突判定从“集合里有没有这个字符”变成“窗口里的不同字符数量有没有超过 K”。再往深处走LeetCode 76 题“最小覆盖子串”是滑动窗口的另一个经典变体它要求找到包含目标字符串所有字符的最短子串。这题用的框架是先扩展右指针让窗口满足条件再收缩左指针寻找最优解。这套“先扩张、后收缩”的顺序跟本题里“遇到重复就收缩左指针”的思路一脉相承。顺着 Hot100 的题单继续刷后续的“腐烂的橘子”BFS 经典题、“基本计算器”栈的经典应用、“爱吃香蕉的狒狒”二分答案的经典题都会反复用到类似的分析方法先确定暴力解法再找冗余计算然后用合适的数据结构优化。刷题不怕慢怕的是只背答案不总结我这次把滑动窗口的来龙去脉写清楚也是希望后面能少走弯路。4. 常见问题与调试心得实录4.1 我踩过的几个典型错解以及为什么错第一个也是最经典的错解就是哈希索引版漏写max。前面用abba验证过直接赋值会让左指针回退窗口变回包含重复字符的非法状态。这个问题我用肉眼看了好久才反应过来最后是打印left、right和窗口内容才定位到的。第二个错解是混淆集合版和索引版。有人把两版代码杂交外层用索引版的map记录位置遇到重复时却用集合版的while循环删除结果left和map的记录对不上窗口长度越算越离谱。两个版本的数据结构是一致的但跳转逻辑完全不同混用必然出错。第三个错解是忘记在每次循环里更新ans。特别是集合版如果只在while循环结束后更新而某些时候冲突循环一次都不执行那就漏掉了窗口增长时的最大长度。更新ans必须放在每次right扩张完成之后和是否发生冲突无关。第四个错解是把“记录字符出现位置”做成“记录字符出现次数”。有些题是数频次但这题要的是位置信息因为我们要精确计算left该跳到哪。如果只记录次数遇到重复时你只知道发生了冲突却不知道冲突字符在窗口的哪个位置左指针只能慢慢挪效率又退回 O(n²) 了。4.2 调试这类题目的小技巧第一招打印三件套。在遍历循环里打印left、right和当前窗口内容s[left:right1]配合abba、abcabcbb、pwwkew这三个用例跑一遍基本能定位 90% 的逻辑错误。打印窗口内容时注意别用s.substring或者切片去参与算法逻辑只用于观察。第二招构造最小复现用例。出错时不要急于看大用例先缩小到一个你能手动推演的长度。比如abba就是我排查max问题时手工构造的它刚好能触发“左指针回退”这个隐蔽 bug。类似的用例还有tmmzuxt这个串的特点是重复字符出现在很靠前的位置但后续字符又把窗口拉长很适合验证max逻辑。第三招用随机小字符串对拍。如果你同时写了一个暴力解和一个滑动窗口解可以写个小脚本随机生成长度不超过 10 的字符串反复对比两个解法的输出。这个方法我在刷字符串题时经常用能一次性发现很多边界问题比肉眼检查高效得多。对拍代码很简单写个暴力函数再写个待验证函数跑 10000 个随机样例。4.3 这道题在面试与刷题路线中的定位“无重复字符的最长子串”在面试中属于高频送分题但它同时也是考察“有没有真正理解滑动窗口”的试金石。很多候选人能默写出哈希索引版的代码但一问到left为什么要用max保护、集合版和索引版复杂度谁更优、数组优化为什么能用char当下标就答不上来了。面试官往往从这些细节判断你是背题还是真懂。如果你是按 Hot100 顺序刷题刷完这道题之后可以马上安排 “3. 无重复字符的最长子串” 同类的滑动窗口题比如 “76. 最小覆盖子串” 和 “438. 找到字符串中所有字母异位词”在一周内连续做三道滑动窗口题模板会印象非常深。我自己刷题的经验是同类题型连续练三到五道比分散刷十道不同题型的效果更好。我个人实际刷这道题时还有个体会每道经典题都要建立自己的“模板笔记”。滑动窗口的笔记我只有四行右指针每次无条件扩张扩张后判断窗口是否合法不合法就收缩左指针直到重新合法每次窗口合法时更新答案。把这四行记熟遇到变体题往里套就行。最后再分享一个小技巧如果面试中时间紧张优先写出哈希集合版因为它逻辑最直观出错的概率低写完再主动提一句“这题还可以用哈希索引版优化常数更小”这比一上来就写索引版更容易让面试官认可你的思路层次。