在LeetCode题库里如果要我选一道“面试中出现频率最高、代码量最少、但能问出花来”的题目那第3题“无重复字符的最长子串”绝对排前三。这道题不仅是我自己当年刷题时的第一道坎也是我后来坐在面试官那一侧时很喜欢考察的一道题。别看它只是让你求一个最长子串的长度背后涉及到的双指针思想、滑动窗口技巧、哈希表应用几乎覆盖了字符串类题目的所有核心考点。很多公司包括国内外大厂都爱拿它做一面手撕代码的题目最近也有不少准备面试的同学跟我提到去吉利面试前端岗位时遇到过这道题要求用JavaScript手写一遍——这题目就是这么经典且高频。这篇文章我会把这道题从暴力解法到最优解法的全路径拆开揉碎包括每一步为什么这么想、代码怎么写、面试时怎么讲以及我自己实际写代码时踩过的各种坑。不管你是刚准备刷题的校招同学还是想系统梳理滑动窗口套路的社招选手这篇内容都能给你一个可以直接“抄作业”的完整方案。1. 理解题意与核心思路设计1.1 先把题目真正读明白“给定一个字符串 s 请你找出其中不含有重复字符的最长子串的长度。”这句话每个字都认识但真的抠起来有几个点必须掰清楚。第一个是“子串”注意不是“子序列”。子串必须是原字符串中连续的一段比如abcabcbb里abc是子串acb就不是因为它们在原字符串里不连续。子序列才允许跳着取但这道题要求的是连续的这个差别直接决定了算法的形状。很多人在面试时思路跑偏往往就是从这两个概念混淆开始的。第二个是“不含有重复字符”。也就是说窗口里任意两个字符不能相同不是说不允许某种字符出现而是所有字符在整个子串内都要唯一。比如pwwkew里答案wke是长度为3的不含重复字符的子串因为w只出现了一次k一次e一次但pwke虽然也不重复它不是连续的子串中间隔着w所以不能算。第三个是要求“长度”不要求返回子串本身。不过面试官经常会追加问一句“那你能返回这个子串吗”这个我后面会单独讲。几个经典的示例可以对照着看输入: abcabcbb输出: 3子串是abc。输入: bbbbb输出: 1子串就是b因为所有字符都一样只能取一个。输入: pwwkew输出: 3子串是wke注意不是pwke。把这三个例子在纸上推一遍题目就理解得七七八八了。1.2 暴力解法想清楚才知道为什么要优化一上来就写滑动窗口的同学其实面试官反而会有点怀疑你是背题的。更好的做法是先把暴力解法的思路说出来然后再推进到优化版本。这样既展示了你的思维过程也让面试官看到你不是在背答案。暴力解法的逻辑不复杂枚举所有可能的子串起点和终点然后检查这个子串里有没有重复字符。如果用最直接的方式三重循环def length_of_longest_substring_v1(s): n len(s) ans 0 for i in range(n): for j in range(i, n): # 检查 s[i:j1] 是否有重复字符 seen set() ok True for k in range(i, j 1): if s[k] in seen: ok False break seen.add(s[k]) if ok: ans max(ans, j - i 1) return ans这个解法的时间复杂度是O(n^3)空间复杂度O(m)m是字符集大小。n是字符串长度。当n稍微大一点比如几千个字符这个算法就明显跑不动了。当然枚举起点终点以后检查重复字符这一层可以用一个哈希表优化掉把内层循环改成边扩展边检查这样能降到O(n^2)代码长这样def length_of_longest_substring_v2(s): 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但O(n^2)在面试中依然算不上一个让人满意的答案。面试官问完复杂度之后90%会继续追问“能不能O(n)解决”。喜欢直接给结论的同学可以现在想想O(n)该怎么做到。1.3 滑动窗口思路是怎么长出来的O(n^2)的解法里每一轮我们都在做一件重复的事固定左端点i然后让右端点j一路向右试探直到碰到重复字符才停下来。发现重复以后下一轮i变成i1重新让j从i1开始试探。注意这里的问题当i1以后前面已经算过的很多字符被浪费了。举个例子s abcabcbb当i0时j能一直走到3发现s[3]a出现在窗口里于是停住。此时窗口是abca重复的字符是a。接下来如果按O(n^2)的思路i变成1j重新从2开始那么b、c这些其实已经被扫过一次了完全可以接着用。滑动窗口的核心洞察就在这里当右指针发现一个重复字符时不需要把左指针一步一步地挪回去重新开始而是直接把左指针跳到“那个重复字符上一次出现位置的下一个位置”。窗口就像一个可以伸缩的滑门右端一直向右扩大左端只在发现重复时才动。这样整个字符串最多被扫描两遍时间复杂度就是O(n)。我个人的体会是滑动窗口这套思路最漂亮的点在于它把“枚举所有子串”变成了“维护一个没有重复字符的窗口”问题从“找最长的那个”变成了“在窗口扩张和收缩过程中记录最大值”。这个视角一旦转过来后面写代码就是一马平川的事。2. 核心细节解析与实操要点2.1 滑动窗口的两种实现方式明确了思路之后代码实现上有两条路线用HashSet记录窗口内字符用HashMap记录字符上次出现的位置。这两种方式在面试里都很常见我挨个说明白。第一种是用HashSet实现“手动滑动”。维护两个指针left和rightright负责扩展窗口每次把新字符s[right]加进窗口之前先判断它是否已经在窗口里如果在就让left一步一步往右挪同时把left经过的字符从set里删除直到把s[right]这个重复字符从窗口里移除。然后再把s[right]加进去更新答案。def length_of_longest_substring_set(s: str) - int: n len(s) seen set() left 0 ans 0 for right in range(n): while s[right] in seen: seen.remove(s[left]) left 1 seen.add(s[right]) ans max(ans, right - left 1) return ans这个实现的好处是逻辑非常直白和滑动窗口的定义一一对应适合在面试时先讲思路。缺点是left是一步一步挪的如果重复字符离left很远中间会多做一些remove操作但整体复杂度仍是O(n)因为left总共只会移动n次。第二种是用HashMap实现“直接跳转”。这里map的key是字符value是“该字符上一次出现的位置”。当发现s[right]已经在map里left可以直接跳到max(left, map[s[right]] 1)。为什么取max因为left只能往右走如果map里记录的旧位置已经在left左边了就不能让left往回退。def length_of_longest_substring_map(s: str) - int: n len(s) pos {} left 0 ans 0 for right in range(n): ch s[right] if ch in pos: left max(left, pos[ch] 1) pos[ch] right ans max(ans, right - left 1) return ans这种实现少了一个while循环代码更紧凑。left指针不是一步步挪而是直接跳到正确位置在重复字符频繁出现时效率更高。2.2 两种实现如何取舍面试官到底想看什么我在实际面试别人时更愿意看到候选人先给出Set版本再主动提到HashMap版本可以优化掉指针逐步移动的过程。这比直接甩一个HashMap版本更能说明“你真的理解滑动窗口而不只是背过答案”。Set版本最大的优势是语义清晰特别适合在讲思路时配合画图解释。当面试官说“如果输入里既有大写又有小写算不算重复”这样的问题时Set版本也最容易通过修改判断逻辑来应对。它的潜在劣势是在极端场景下比如字符串是abcdefghijklmnopqrstuvwxyz然后一直循环left每次都要跳很长一段距离虽然总复杂度还是O(n)但每一步的赋值操作确实是HashMap版本的两三倍。HashMap版本的主要优势是left跳转是O(1)的且代码看起来更“聪明”。但聪明也意味着容易出错比如漏掉max(left, ...)这个保护或者忘记在更新ans之前已经修改了left。我见过不少候选人把HashMap版本写对以后被面试官追问“为什么这里要取max不取会怎样”的时候卡住原因就是没有真正理解left的单调性约束。给一个实用建议如果你面试时时间紧张直接写Set版本最稳不容易出bug如果你想把代码写得漂亮优先HashMap版本但务必在写之前就把max的逻辑讲清楚。两个版本的实际运行时间差距在普通输入上几乎可以忽略面试时算法正确性和思路清晰度远比这种微优化重要。2.3 多语言实现参考含JavaScript版本面试是分语言的前端同学通常要求用JavaScript手写后端同学用Java、Go、C都很常见。我统一整理一下方便大家按需取用。JS版本吉利这类公司的前端面试题就喜欢这么考var lengthOfLongestSubstring function(s) { let pos new Map(); let left 0; let ans 0; for (let right 0; right s.length; right) { const ch s.charAt(right); if (pos.has(ch)) { left Math.max(left, pos.get(ch) 1); } pos.set(ch, right); ans Math.max(ans, right - left 1); } return ans; };Java版本public int lengthOfLongestSubstring(String s) { MapCharacter, Integer pos new HashMap(); int left 0; int ans 0; for (int right 0; right s.length(); right) { char ch s.charAt(right); if (pos.containsKey(ch)) { left Math.max(left, pos.get(ch) 1); } pos.put(ch, right); ans Math.max(ans, right - left 1); } return ans; }C版本int lengthOfLongestSubstring(string s) { unordered_mapchar, int pos; int left 0, ans 0; for (int right 0; right s.size(); right) { char ch s[right]; if (pos.count(ch)) { left max(left, pos[ch] 1); } pos[ch] right; ans max(ans, right - left 1); } return ans; }这三个版本逻辑完全一致都是用HashMap记忆成本很低。如果你日常用Go把Java换成Go的map[string]int也是同样套路。2.4 复杂度分析别只会说“是O(n)”很多候选人能写出代码但一被问复杂度就只会说“嗯这是O(n)”这就浪费了展示自己的机会。正确的回答方式应该是先解释复杂度再给出严谨的理由。时间复杂度O(n)right指针从0到n-1遍历一遍left指针虽然可能移动但left始终单调不减在整段代码里left最多移动n次。窗口的每个字符进入窗口一次移除窗口最多一次所以总操作次数是O(n)。空间复杂度O(c)c是字符集的大小而不是n。这里有个容易混淆的点HashMap里存的是每个字符上一次出现的位置字符的种类数是有限的。如果题目说明输入只包含小写字母那c26如果没说明按ASCII字符集算c128或者256如果按Unicode算理论上会更大但实际字符种类也是常数级的不会随着字符串长度n增长。所以空间复杂度是O(c)在很多资料里也直接写成O(1)。如果你能把复杂度分析说到这个颗粒度面试官通常就不会再揪细节了。3. 实操过程与核心环节实现3.1 手动推演一遍窗口的变化过程代码写出来不难但真正理解它为什么对最好还是在纸上把窗口的伸缩过程画一遍。我用abcabcbb这个例子完整走一遍大家更直观。初始化left0, ans0, pos为空。right0chapos里没有a记录pos[a]0窗口是[0,0]长度1ans1。right1chbpos里没有b记录pos[b]1窗口是[0,1]长度2ans2。right2chcpos里没有c记录pos[c]2窗口是[0,2]长度3ans3。right3chapos里有a且pos[a]0left变成max(0, 01)1。记录pos[a]3窗口是[1,3]也就是bca长度3ans保持3。right4chbpos里有b且pos[b]1left变成max(1, 11)2。记录pos[b]4窗口是[2,4]也就是cab长度3ans保持3。right5chcpos里有c且pos[c]2left变成max(2, 21)3。记录pos[c]5窗口是[3,5]也就是abc长度3ans保持3。right6chbpos里有b且pos[b]4left变成max(3, 41)5。记录pos[b]6窗口是[5,6]也就是cb长度2ans保持3。right7chbpos里有b且pos[b]6left变成max(5, 61)7。记录pos[b]7窗口是[7,7]也就是b长度1ans保持3。最终返回ans3。这个推演里可以看到left确实一直在往右走从0走到7中间没有回退过。这就是滑动窗口和暴力枚举最本质的区别。3.2 面试追问与变体不只是求长度面试官在你说完基本解法之后非常喜欢追加变体。我梳理几个最高频的追问建议大家提前准备。第一个追问返回最长无重复子串本身而不是长度。解法思路是当更新ans时同时记录当前的left和right最后用s.substring(left, right1)取出来。注意更新ans的时机别在left移动前就记录了窗口那样会拿错。var longestSubstring function(s) { let pos new Map(); let left 0, maxLen 0, start 0; for (let right 0; right s.length; right) { const ch s.charAt(right); if (pos.has(ch)) { left Math.max(left, pos.get(ch) 1); } pos.set(ch, right); if (right - left 1 maxLen) { maxLen right - left 1; start left; } } return s.substring(start, start maxLen); };第二个追问如果字符串包含中文怎么办还适用吗适用于HashMap/Map的方案因为key是字符本身不管ASCII还是Unicode都能处理。但如果你用了int[128]这样的数组优化那么只有ASCII字符能正确处理中文就不行了。我看到很多网上题解为了追求快用int[128]存字符位置这个在面试现场写出来其实是有风险的因为面试官只要追加一句“输入包含emoji怎么办”就能让你卡壳。第三个追问能不能不用额外空间这个变体本质上是想考你怎么用O(1)空间做。思路是如果字符集固定且有限比如只有小写字母可以用一个长度为26的数组记录每个字符上一次出现的位置来代替HashMap。但如果在面试时说“不用额外空间”这通常是做不到的因为最坏情况你总得记录窗口内有哪些字符。实际面试中这种追问考察的是你对复杂度边界的认知明确说出来“在字符集有限的前提下可以用数组优化到O(c)空间但严格O(1)不现实”就已经能得分了。3.3 面试现场怎么讲这道题这道题代码量不大但想拿高分讲解顺序很重要。我自己总结了一套在面试中比较稳的讲述流程。第一步先复述题意确认边界。不要急着写代码先和面试官对齐“题目要求的是连续子串子串内所有字符不能重复返回最大长度”。如果面试官说“输入可能为空字符串”你就说空字符串返回0单字符返回1这些边界随手就能处理。第二步给出暴力解法作为起点并且主动分析复杂度。说“我可以先枚举起点和终点再用集合判断是否有重复复杂度O(n^3)简单优化后O(n^2)”这时面试官通常会说“你来个更优的解法”。第三步引出滑动窗口优化。讲“当右指针遇到重复字符时不需要从头开始枚举只需要把左指针移动到上次出现位置的下一个位置因为中间这些字符组成的新子串长度不会超过当前已经记录的答案”。第四步边写边讲。我个人的经验是先声明变量含义再写循环再写更新逻辑。每写几行就同步说一句这段在干什么避免写完一坨代码再统一解释。面试官不需要你默写需要的是能看出你的思考路径。第五步主动做测试。写完代码以后用输入abcabcbb亲自跑一遍主要逻辑证明没有明显的bug再补充测试空串和单字符的情况。这个习惯非常加分很多候选人代码写完就沉默等面试官来挑错观感完全不同。4. 常见问题与排查技巧实录4.1 典型错误速查表我刷这道题以及看别人面试写这道题时整理了一些高频错误做成表格方便大家对照排查。错误现象根本原因解决方式返回结果比预期大把不连续的子序列也算进去了确认窗口始终是全连续区间别在中间跳过字符重复字符出现在窗口内但没被检测到用了数组但字符集覆盖不全改用HashMap或确保数组大小覆盖所有可能输入left跳过头窗口变成负长度更新left时没有取max导致left回退始终使用left max(left, pos[ch] 1)长度一直不变ans始终为0忘记更新ans或者更新时机不对每次right扩展后都要计算right-left1并更新ans用Set版本但跳出while后没把当前字符加进去只判断了不重复才加漏了所有重复字符出现时也要加无论是否重复完成left移动后都要把s[right]加入窗口空字符串返回了null或报错没有处理n0的边界初始化ans0循环不会执行直接返回ans这张表里最容易踩的是第三行和第五行。第三行对应HashMap版本很多初学者写left pos[ch] 1忘了和当前left取max一旦遇到已经滑过去的旧位置left就会回退窗口长度甚至变成负的得到的答案完全错乱。第五行对应Set版本特别容易在while跳出后忘记add当前字符导致少算一个字符。4.2 我实际踩过的三个坑先说第一个坑HashMap版本里漏了max保护。我第一次写的时候输入abbaleft在right3时遇到a此时pos[a]0如果直接leftpos[a]11而当前left2窗口会从2退到1子串变成bb这明显是错误的因为窗口内包含了两个a但left却退回到第二个b处。这个bug非常隐蔽因为left回退一步看起来好像只是边界问题但实际上整个窗口的语义就崩了。从那以后我给自己立了个规矩凡是更新left的代码必须先检查是否保证单调性。第二个坑用int[128]数组处理非ASCII字符。有一段时间我看到题解里写int[128]很羡慕觉得又快又省空间于是自己面试时写了一遍。结果面试官追问了一句“如果字符串包含中文字符呢”当时就愣了。中文在Unicode里的编码远超128int[128]数组会直接越界。后来我明白了像LeetCode这种题测试用例默认是ASCII但真实工程的字符串什么都有HashMap其实是最稳妥的通用方案。要展示优化用一句话带过“如果确定是ASCII可以用int[128]降到O(1)空间”就够了代码里还是要写安全的版本。第三个坑更新答案的时机。有一版我写的是在left移动之前先记录长度导致窗口内仍然包含重复字符时也更新了ans于是答案偏大。正确的思路应当是先把重复字符挤出去再统计窗口长度。这和执行顺序有关很多人背代码背得滚瓜烂熟但一旦让手推一个例子就会出错根源就在这里。4.3 测试用例设计清单一道手撕代码题如果你能主动提出一套测试用例面试官会相当满意。针对这道题我常用的测试集是这些空字符串期望0。单字符a期望1。全相同字符aaaaa期望1。全不相同字符abcdefg期望7。重复字符在开头abca期望3。重复字符在中间abccba期望3。重复字符在结尾abcabc期望3。经典示例abcabcbb期望3。经典示例pwwkew期望3。包含空格和标点a b c a期望3注意Shell输入时需转义。包含中文abc你好你d期望5。这里特别说下最后一个如果你用HashMap版本中文完全没问题如果你当时图省事用了int[128]测试用例就会挂掉。这也是我为什么反复强调在面试里优先写HashMap的版本不是因为它性能好而是因为它适用于更广泛的输入这才是生产级代码该有的样子。5. 从一道题到一类题滑动窗口的扩展这道题解出来以后千万别急着跳到下一道新题。滑动窗口是一类题的骨架把这道题吃透了后面LeetCode 76最小覆盖子串、LeetCode 567字符串的排列、LeetCode 438找到字符串中所有字母异位词都能用相似的套路去套只是窗口的收缩条件从“有重复字符”变成了“窗口不满足某种排列要求”而已。我自己常用的一套滑动窗口模板是这样的# 右指针遍历 for right in range(len(s)): # 1. 把当前字符加入窗口 # 2. 当窗口不满足约束时移动left直到窗口重新满足 # 3. 窗口满足约束时更新答案核心要义只有一句话确定“窗口不满足条件”的判定逻辑然后让left在条件不成立时向右收缩right始终负责扩张。在无重复字符这道题里不满足条件是“有重复字符”判定用Set或Map在最小覆盖子串里不满足条件是“窗口尚未覆盖t中所有字符”判定用一个计数数组记录字符差在字符串排列里不满足条件是“窗口长度大于目标串长度”或“字符计数不匹配”。骨架一致差异只在判定逻辑。如果你刷题时间有限我强烈建议先把这道题做到“闭着眼能写讲解时能说清每一步为什么”然后再去碰后面三道扩展题。滑动窗口这个类型在面试里的出现频率可能仅次于数组排序和二叉树遍历把它拿下性价比极高。最后再分享一个小技巧练习这类题目时不要只在编辑器里运行通过就完事。试着在博客、笔记里把窗口的每一步变化过程写出来哪怕只是简单记录left、right和当前字符都会帮你把“窗口的移动逻辑”变成肌肉记忆。等到面试场上你根本不需要临时推理手会自然地写出来。说到底算法面试考的不是刷题数量而是你有没有把一道题吃透。把这道无重复字符的最长子串吃透你迈出的这一步绝对值回票价。