无重复字符的最长子串一道题看懂滑动窗口面试这样答才算过关如果你最近在准备算法面试十有八九会碰到这道题——无重复字符的最长子串。我在帮朋友做面试复盘时发现这道题几乎是大厂前端岗、后端岗的高频题尤其是JS岗位问得特别勤。原因很简单它看起来不难但能同时考察你对字符串处理、哈希表的使用、指针移动的逻辑以及复杂度分析的掌握程度一题能问出好几层水平。这道题的意思是给定一个字符串找出其中不含有重复字符的最长子串的长度。比如输入abcabcbb输出是3因为最长无重复子串是abc长度为3输入bbbbb输出是1输入pwwkew输出是3最长是wke或kew。注意是子串不是子序列所以必须是连续的。无论你是刚开始刷题的初学者还是准备冲刺大厂面试的求职者这道题都值得花时间吃透。下面我会从暴力解法开始讲起到滑动窗口的两种常见实现再到面试问答的加分表达最后分享我实际写代码时踩过的坑。全程用JavaScript演示因为这是前端面试最常用的语言而且JS在处理字符串和哈希结构时有自己的特性值得单独拿出来讲。1. 题目拆解先搞清楚题目到底在问什么很多人拿到这道题就开始写代码结果写着写着发现边界条件处理不对。我建议你先花两分钟把题目拆清楚这比多写十遍代码都管用。1.1 三个关键词最长、无重复、子串“最长”意味着我们要在所有可能的答案里取最大值所以代码里必然有一个max变量在持续更新“无重复”意味着我们需要一种数据结构来记录哪些字符已经出现过了“子串”则限定必须是连续的字符片段不是可以跳着选的子序列。把这三个词翻译成代码需求我们需要在字符串上维护一个连续的区间保证区间内所有字符互不相同并且让这个区间的长度尽可能大过程中不断更新最大值。我见过不少人在“子串”和“子序列”上栽跟头。比如字符串abcbd如果题目问的是无重复字符的最长子序列答案是4abcd因为可以跳着选但如果是子串答案是3abc或cbd因为必须连续。这道题明确说了是子串所以滑动窗口这种基于连续区间的方案才适用。1.2 边界情况空字符串和单字符先看两个极端情况。输入是空字符串时没有任何子串答案应该是0输入是单个字符a时最长无重复子串就是它自己答案是1。这两个边界必须在一开始就处理好否则后续代码很容易在空串上报错。再看全重复的情况比如aaaa答案是1因为你只能取一个a全不重复的情况比如abcd答案是4因为整个字符串本身就是无重复的。还有一个容易忽略的情况数字和字母混在一起比如a1b2a1字符1和a都会重复处理逻辑通用不需要特殊区分字符类型。我把这类测试用例整理成一个速查表写代码前和写代码后都可以对照着验证输入预期输出说明0空串没有子串a1单个字符自成一个子串aaaa1全重复abcd4全不重复abcabcbb3经典示例答案是abcpwwkew3答案是wke或kewdvdf3答案是vdf注意d重复abba2答案是ab或ba双指针边界要小心abba这个用例特别经典我后面会专门说明为什么它能测出很多错误写法。2. 从暴力解到滑动窗口思路是怎么一步步演进的面试官真正看重的不只是你会不会写这道题而是你怎么从最直观的思路开始逐步优化到最优解。所以你自己心里要有一条清晰的演进路线。2.1 暴力解能跑但只能跑通示例最直观的想法是枚举所有子串逐个检查每个子串里有没有重复字符记录最长长度。用代码来说就是两层循环固定子串的起点i和终点j再用一个辅助结构检查从i到j这段字符是否全部无重复。function lengthOfLongestSubstring(s) { if (s.length 1) return s.length; let max 0; for (let i 0; i s.length; i) { for (let j i; j s.length; j) { const sub s.slice(i, j 1); if (new Set(sub).size sub.length) { max Math.max(max, sub.length); } } } return max; }这段代码简洁、能跑示例都过得了但性能非常差。三层嵌套的复杂度是O(n³)其中两层循环枚举起点终点是O(n²)new Set(sub)检查重复又是O(k)k为子串长度加起来就是三次方的级别。字符串一长比如几千个字符代码基本就跑不动了。很多面试者止步于此但面试官要看到的显然不只是这个版本。暴力解真正的价值在于它帮我们确立了核心目标在枚举所有子串的过程中如何快速判断“从i到j这段没有重复字符”以及如何避免重复枚举那些已经被判断过的区间。2.2 滑动窗口把O(n³)降到O(n)的关键洞察我们仔细看暴力枚举的过程会发现大量计算是重复的。比如i0, j2时已经知道s[0..2]没有重复那判断i0, j3时理论上只需要检查新进来的s[3]有没有在s[0..2]中出现过而不是把s[0..3]整体重新检查一遍。这就引出了滑动窗口维护一个区间[left, right]保证区间内没有重复字符每次把右边界向右扩展如果新字符没出现过就加入窗口如果出现过就把左边界向右移动直到移除与新字符重复的那个旧字符为止。窗口像一个可伸缩的滑轨始终只保存“当前这截无重复字符”并在这个过程中不断记录窗口的最大长度。这样的时间复杂度是多少左右两个指针各遍历一次数组所以是O(n)空间上需要一个哈希结构记录字符出现情况最坏情况是O(n)。这个增量式的思路就是滑动窗口算法的精髓它不再重复枚举所有区间而是让区间在移动的过程中自然覆盖所有可能的无重复子串。3. JavaScript实现三套方案代码与细节对比下面进入实操环节。我给出三种JavaScript实现从最容易理解到性能最优每种都附上代码、复杂度分析以及我实际使用下来的体会。建议你先跟着敲一遍再对照差异思考为什么。3.1 方案一基于Set的滑动窗口这是最容易理解、也最贴合“窗口”直觉的写法。窗口内维护一个Set右指针不断右移遇到重复字符时左指针跟着右移同时从Set里删除移出的字符。function lengthOfLongestSubstring(s) { const set new Set(); let left 0; let max 0; for (let right 0; right s.length; right) { const ch s[right]; while (set.has(ch)) { set.delete(s[left]); left; } set.add(ch); max Math.max(max, right - left 1); } return max; }核心逻辑就三句话遇到重复就先收缩左边界直到不重复把新字符加入窗口然后更新答案。这里的while循环可能让人觉得最坏情况会变慢但实际上每个字符最多被加入和删除一次均摊下来还是O(n)。这种写法的好处是语义清晰面试时讲“窗口、移动、收缩”都方便。缺点是每次都靠while一点点挪左指针如果遇到大量重复字符挪动的次数会多一些虽然不影响整体复杂度但常数项上稍逊于后面的哈希表版本。另外一定要注意set.delete(s[left])删的是“从左边移出的那个字符”不是刚才ch重复的那个字符这两者可能不同。想清楚这一点是写对这道题的关键。3.2 方案二基于Map的索引跳跃优化既然左指针可以一次性跳到位为什么还要一点点挪用Map保存每个字符最近一次出现的索引遇到重复时直接让left跳到重复字符上一次出现的后一个位置即可。这比Set版本少了while循环。function lengthOfLongestSubstring(s) { const map new Map(); let left 0; let max 0; for (let right 0; right s.length; right) { const ch s[right]; if (map.has(ch) map.get(ch) left) { left map.get(ch) 1; } map.set(ch, right); max Math.max(max, right - left 1); } return max; }这里关键的一行是map.get(ch) left。为什么要加这个判断因为Map里存的索引有可能是旧的、已经不在当前窗口内的位置。比如s abba遍历到第3个字符a时map里a存的是索引0但此时窗口左边界已经挪到了2索引0已经不在窗口里了。如果不加这个判断left会被错误地跳回到1导致结果出错。加了 left判断之后只有重复字符确实出现在当前窗口内索引大于等于左边界才更新左指针。这是Map版本最容易写错的地方也是面试官最高频的追问点之一。3.3 方案三直接存索引的极简写法既然字符本质上可以用数组下标表示那我们也可以用普通数组模拟哈希表空间上可能更省。这种写法在字符集固定比如只有ASCII字符的场合非常高效。function lengthOfLongestSubstring(s) { const indexMap new Array(128).fill(-1); let left 0; let max 0; for (let right 0; right s.length; right) { const code s.charCodeAt(right); if (indexMap[code] left) { left indexMap[code] 1; } indexMap[code] right; max Math.max(max, right - left 1); } return max; }数组indexMap的长度取128是因为ASCII字符集共128个字符s.charCodeAt(right)拿到的就是字符的编码。如果题目明确说明只会出现小写字母可以缩到26如果可能包含中文或Unicode字符就不能用这个方案了得回到Map。这里有个取舍数组访问比Map的哈希计算更快所以纯ASCII环境下这个写法是性能最优的但它牺牲了通用性。三套方案选哪套上考场我的建议是第一套Set版本用于讲思路第三套数组版本用于炫技第二套Map版本最稳妥。面试时你先把Set版讲清楚再在优化环节改成Map版或数组版就能体现出“从容易理解到高效实现”的完整思考链条。4. 面试现场从写对到写出竞争力纯粹把代码贴出来并不是面试的终点。我陪练过很多候选人发现同样是写对这道题有的人能拿strong hire有的人只是average。差别在于他们怎么讲述自己的思路以及有没有准备好面试官的追问。4.1 面试时的表达顺序和技巧面试官让你做题时不要拿到题就闷头敲键盘这会给对方“背答案”的感觉。更好的做法是先花一两分钟确认题意然后口头说一遍思路再动手。就这道题而言你可以这样说“我准备用一个滑动窗口来解。窗口内维护的是一段无重复字符的子串右指针负责扩展左指针负责在遇到重复时收缩。我用一个哈希表记录每个字符最近一次出现的位置这样收缩时可以一次性跳到位。整个过程只需要遍历一次字符串时间复杂度O(n)空间复杂度O(n)。”这段话有信息量但不啰嗦能把核心思路、数据结构、复杂度一次讲清楚。面试官听到这里基本上就知道你不是第一次做这道题了。然后开始写代码。写的时候建议先用Set版本起步因为它的逻辑对应你的口头描述最直接。写完跑一遍示例再自然地说一句“如果想进一步优化可以把Set换成Map存索引这样左指针可以直接跳到位”然后把代码升级成Map版本。这一“写两版”的动作用时不多但能充分展示你的优化意识。4.2 常见追问扩展题与变形题怎么接面试官大概率会追问一些变种题目的是试探你是真懂了还是只背了模板。我遇到过且实际被问过的变体主要有三种。第一种是让你返回最长的无重复子串本身而不是长度。解法是在更新max时同时记录起始索引循环结束后通过substring截取。这个变体考察的是你是否理解“答案藏在哪一步更新”——其实每一步更新的[left, right]区间都有可能是最终答案只是长度目前不是最大所以要做一次截取。第二种是扩展到“至多K个不同字符的最长子串”。这个变体在字节、微软的面试中很常见思路仍然是滑动窗口但右侧进入字符时如果窗口内的不同字符数超过K就收缩左边界直到满足条件。收缩时用一个哈希表统计字符出现次数当某个字符计数减到0时从哈希表删除然后判断不同字符数量是否降回K。它的核心逻辑和原题几乎同源只是“重复检测”换成了“不同字符计数”。第三种是“最短覆盖子串”LeetCode第76题它是这道题的镜像问题给定一个源串和一个目标串找到包含目标串所有字符的最短子串。解法和无重复字符类似但逻辑相反——右边扩展时是凑齐目标字符左边收缩时改善结果用两个哈希表做计数匹配。这个难度高一些但如果前两个变体你都接得住就是很大的加分项。我整理了一个追问速查表方便你临考前快速回顾追问形式考察点应答要点为什么用滑动窗口而不是暴力复杂度分析暴力O(n³)滑动窗口O(n)增量式判断替代重复枚举用Set和用Map的区别数据结构选型Set逐位收缩Map索引跳跃Map更优但要注意旧索引判断左指针跳转时为什么要判断 left边界正确性Map里可能留有窗口外的旧索引不判断会错误收缩窗口如果字符集是Unicode怎么办通用性Map可以处理任意字符数组方案受限于固定字符集要求返回子串本身变体实现更新max时记录起始索引最后截取字符串长度达到10^6怎么办极端输入必须用O(n)方案且注意减少常数甚至可以用字符编码数组优化5. 踩坑实录与常见问题排查这一节我想分享一些我实际写代码、给候选人改代码时遇到的真实错误。很多问题在题解文章里看不到但在面试考场上几乎一定会冒出来值得提前预防。5.1 我自己踩过的几个坑第一个坑是Map版本的 left判断漏掉。我第一次写这种“索引跳跃”写法时循环里只写了if (map.has(ch)) left map.get(ch) 1;没有判断旧索引是否在当前窗口内结果跑abba这个用例时输出了4而不是2。原因是遍历到最后一个a时Map里a对应的索引是0但窗口早就越过它了left被错误地拉了回去。这个错误特别隐蔽因为示例测试不一定会覆盖到但一旦覆盖就必挂。第二个坑是Set版本里while循环写成了if。if只处理一次重复如果窗口里同时有两个相同的字符连续重复if只删一个就走了后面set.add(ch)又加了一个窗口里依然有重复答案就错了。比如abcabcbb里当right走到第二个b时如果用if左指针只会放弃最左边的a窗口里还剩一个a一个b的旧副本逻辑直接破功。必须用while循环一直收缩直到窗口里没有和ch重复的字符。第三个坑是for...of遍历字符串时拿不到索引。如果写成for (const ch of s)循环体里只能用indexOf之类的方法去查索引效率变差代码也绕。建议直接用for (let right 0; right s.length; right)索引和字符都握在手里踩坑概率低很多。5.2 常见问题速查表自测你的代码有没有问题每次写完这道题你可以用下面这张表快速检查自己的代码有没有踩到常见错误。常见问题原因解决办法输出比预期大左指针收缩逻辑错误窗口内仍有重复字符检查while是否真正把重复字符移出窗口输出比预期小初始化max为0但没考虑空串之外的边界max初始为0没问题但确认最后一个窗口也被比较了Map版本在abba上出错旧索引未判断是否在窗口内加上map.get(ch) left判断用例全过但超时暴力解或频繁slice换成滑动窗口避免每次截取子串用数组存储索引时越界charCodeAt超过数组长度明确题目字符集范围或改用Map字符串含Unicode字符用s.codePointAt处理可能更好严格场景下用Map最稳面试时讲不清为什么O(n)不理解均摊分析可从“每个字符最多被加入和移除一次”的角度解释这个表我建议你用来自检不止面试前平时刷题时也可以贴在手边。我自己的习惯是每写完一个解法至少跑一遍表里的测试用例特别是、 、abba、dvdf这些容易被忽略的输入。最后说一个特别实用的经验这道题刷三遍还不够要刷到“不看代码能画出窗口移动过程”的程度。我面试别人时发现很多人代码能写对但被问到“某一时刻窗口里具体有哪几个字符”时却说不上来说明他们的脑内模拟不够熟练。建议你用abcabcbb手动模拟一遍整个过程把每一步的left、right、窗口内容、max记下来这个过程只要做一次很多细节就内化了。这个练习我个人非常推荐比多刷十道同类题都管用。