企业官网建设流程全解析

无重复字符的最长子串：一道题看懂滑动窗口，面试这样答才算过关

如果你最近在准备算法面试，十有八九会碰到这道题——无重复字符的最长子串。我在帮朋友做面试复盘时发现，这道题几乎是大厂前端岗、后端岗的高频题，尤其是JS岗位，问得特别勤。原因很简单：它看起来不难，但能同时考察你对字符串处理、哈希表的使用、指针移动的逻辑，以及复杂度分析的掌握程度，一题能问出好几层水平。

这道题的意思是：给定一个字符串，找出其中不含有重复字符的最长子串的长度。比如输入"abcabcbb"，输出是3，因为最长无重复子串是"abc"，长度为3；输入"bbbbb"，输出是1；输入"pwwkew"，输出是3，最长是"wke"或"kew"。注意是子串，不是子序列，所以必须是连续的。

无论你是刚开始刷题的初学者，还是准备冲刺大厂面试的求职者，这道题都值得花时间吃透。下面我会从暴力解法开始讲起，到滑动窗口的两种常见实现，再到面试问答的加分表达，最后分享我实际写代码时踩过的坑。全程用JavaScript演示，因为这是前端面试最常用的语言，而且JS在处理字符串和哈希结构时有自己的特性，值得单独拿出来讲。

1. 题目拆解：先搞清楚题目到底在问什么

很多人拿到这道题就开始写代码，结果写着写着发现边界条件处理不对。我建议你先花两分钟把题目拆清楚，这比多写十遍代码都管用。

1.1 三个关键词：最长、无重复、子串

“最长”意味着我们要在所有可能的答案里取最大值，所以代码里必然有一个max变量在持续更新；“无重复”意味着我们需要一种数据结构来记录哪些字符已经出现过了；“子串”则限定必须是连续的字符片段，不是可以跳着选的子序列。

把这三个词翻译成代码需求：我们需要在字符串上维护一个连续的区间，保证区间内所有字符互不相同，并且让这个区间的长度尽可能大，过程中不断更新最大值。

我见过不少人在“子串”和“子序列”上栽跟头。比如字符串"abcbd"，如果题目问的是无重复字符的最长子序列，答案是4（"abcd"），因为可以跳着选；但如果是子串，答案是3（"abc"或"cbd"），因为必须连续。这道题明确说了是子串，所以滑动窗口这种基于连续区间的方案才适用。

1.2 边界情况：空字符串和单字符

先看两个极端情况。输入是空字符串""时，没有任何子串，答案应该是0；输入是单个字符"a"时，最长无重复子串就是它自己，答案是1。这两个边界必须在一开始就处理好，否则后续代码很容易在空串上报错。

再看全重复的情况，比如"aaaa"，答案是1，因为你只能取一个'a'；全不重复的情况，比如"abcd"，答案是4，因为整个字符串本身就是无重复的。还有一个容易忽略的情况：数字和字母混在一起，比如"a1b2a1"，字符'1'和'a'都会重复，处理逻辑通用，不需要特殊区分字符类型。

我把这类测试用例整理成一个速查表，写代码前和写代码后都可以对照着验证：

"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)的关键洞察

我们仔细看暴力枚举的过程，会发现大量计算是重复的。比如i=0, j=2时已经知道s[0..2]没有重复，那判断i=0, j=3时，理论上只需要检查新进来的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题），它是这道题的镜像问题：给定一个源串和一个目标串，找到包含目标串所有字符的最短子串。解法和无重复字符类似但逻辑相反——右边扩展时是凑齐目标字符，左边收缩时改善结果，用两个哈希表做计数匹配。这个难度高一些，但如果前两个变体你都接得住，就是很大的加分项。

我整理了一个追问速查表，方便你临考前快速回顾：

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 常见问题速查表：自测你的代码有没有问题

每次写完这道题，你可以用下面这张表快速检查自己的代码有没有踩到常见错误。

这个表我建议你用来自检，不止面试前，平时刷题时也可以贴在手边。我自己的习惯是：每写完一个解法，至少跑一遍表里的测试用例，特别是""、" "、"abba"、"dvdf"这些容易被忽略的输入。

最后说一个特别实用的经验：这道题刷三遍还不够，要刷到“不看代码能画出窗口移动过程”的程度。我面试别人时发现，很多人代码能写对，但被问到“某一时刻窗口里具体有哪几个字符”时却说不上来，说明他们的脑内模拟不够熟练。建议你用"abcabcbb"手动模拟一遍整个过程，把每一步的left、right、窗口内容、max记下来，这个过程只要做一次，很多细节就内化了。这个练习我个人非常推荐，比多刷十道同类题都管用。