读完本文你将了解最长无重复子串的 3 种解法演进 | 滑动窗口模式的核心原理 | 面试中的常见变体 题目原题LeetCode 3给定一个字符串s找出其中不含重复字符的最长子串的长度。项目说明输入s “abcabcbb”输出3解释最长无重复子串是 “abc”长度为 3约束0 ≤ s.length ≤ 5×10⁴s 由英文字母、数字、符号和空格组成 先问一个问题第一次给 AI 看这道题它会怎么写大多数人第一反应是遍历所有子串检查每个子串是否包含重复字符。AI 也一样。不是因为它笨人的直觉就是这样思考的。 第一版AI 的朴素解法暴力枚举deflength_of_longest_substring(s:str)-int:暴力枚举所有子串O(n³)nlen(s)max_len0foriinrange(n):forjinrange(i,n):iflen(set(s[i:j1]))j-i1:max_lenmax(max_len,j-i1)returnmax_len这个代码能跑但面试官看了会直接叫停。三层嵌套外层循环起点 i内层循环终点 jset()内部又是一层隐式循环。总复杂度 O(n³)n50000 时完全不可用。复杂度分析时间 O(n³) 空间 O(min(n, ∣Σ∣)) AI 的自我优化第 1 次优化滑动窗口 O(n²)AI 很快意识到不需要每次都重建set。改用两个指针维护一个窗口窗口内保证无重复字符deflength_of_longest_substring(s:str)-int:滑动窗口 setO(2n)nlen(s)char_setset()left0max_len0forrightinrange(n):whiles[right]inchar_set:char_set.remove(s[left])left1char_set.add(s[right])max_lenmax(max_len,right-left1)returnmax_len从 O(n³) 降到 O(2n) ≈ O(n)。不再每次从零检查子串而是让 left 指针追赶 right 指针保证窗口内始终无重复。但这里有个问题——while 循环中每次只移除 left 指向的字符如果重复字符在窗口中间而不是左端需要多次循环才能移除。暴力枚举O(n³)滑动窗口setO(2n)优化版HashMap直接跳转 leftO(n)第 2 次优化HashMap 直接跳转 O(n)真正的最优解是用 HashMap 记录每个字符最近出现的位置遇到重复时直接跳转 leftdeflength_of_longest_substring(s:str)-int:HashMap 记录字符位置O(n) 一次遍历char_index{}left0max_len0forright,chinenumerate(s):ifchinchar_indexandchar_index[ch]left:leftchar_index[ch]1char_index[ch]right max_lenmax(max_len,right-left1)returnmax_len从 O(2n) 降到精确 O(n)——left 指针不再一步步挪而是一次跳到位。这是滑动窗口模式中最核心的技巧不要用 while 循环逐步收缩窗口用 HashMap 直接定位跳转点。☕ Java 实现思路完全一致publicintlengthOfLongestSubstring(Strings){MapCharacter,IntegercharIndexnewHashMap();intleft0;intmaxLen0;for(intright0;rights.length();right){charchs.charAt(right);if(charIndex.containsKey(ch)charIndex.get(ch)left){leftcharIndex.get(ch)1;}charIndex.put(ch,right);maxLenMath.max(maxLen,right-left1);}returnmaxLen;}为什么要加 JavaCSDN 第一大用户群体是 Java 开发者。Python 能看懂不代表面试能用 Java 写出来。两版代码摆在一起读者自己对比比讲十句话都有用。 算法模式拆解这道题是典型的滑动窗口Sliding Window模式。是否否是初始化 left0, max_len0扩展 right, 记录字符位置字符重复且在窗口内?left 跳到重复位置1更新 max_lenright 遍历完?返回 max_len模式识别滑动窗口解决的是连续子序列/子数组问题核心特征特征本题表现问题要求连续子串天然连续窗口边界可变left/right 动态调整窗口内需满足约束无重复字符求最大/最小/最优值求最大长度通用模板defsliding_window(s):滑动窗口通用模板left0result0window{}forright,chinenumerate(s):window[ch]window.get(ch,0)1while不满足约束条件:remove window[s[left]]left1resultmax(result,right-left1)returnresult模式变体最多包含 K 个不同字符的最长子串LeetCode 340约束从无重复变为最多 K 种字符最小覆盖子串LeetCode 76约束变为包含目标字符串的所有字符无重复字符的最长子数组字符换成数字逻辑完全一致️ 真实产品场景这个模式在实际产品中无处不在Slack 的会话超时检测每个用户有一个活跃会话 Token服务器需要检测一个 Token 序列中最长的不重复 Token 段——和本题一模一样。如果检测到重复 Token 出现在同一个会话窗口内说明 Token 被重放攻击了。Netflix 的推荐多样性当为用户推荐视频列表时需要保证连续推荐中不出现重复的类别或演员。这本质上就是在维护一个无重复滑动窗口。Google 搜索的连续查询去重用户在短时间内反复搜索相同的关键词搜索结果页需要识别并折叠这些重复查询只保留最新的一次。✅ 面试官的点评通过标准保底分能写出滑动窗口 set 的 O(2n) 版本能说清楚为什么暴力解不可用能分析时间复杂度加分项冲满分写出 HashMap 跳转版 O(n)这才是面试官想看到的能处理字符集不限于 ASCII问一句输入字符集有多大——如果支持 Unicode 全部字符HashMap 比固定数组更合适边界条件处理空字符串返回 0单字符返回 1主动聊产品场景说出上面的 Slack/Netflix 场景面试官会点头常见踩坑用 int[128] 代替 HashMap仅限 ASCII不是通用解while 循环中 left 而非直接跳转多耗常数时间但面试中可接受忘记检查char_index[ch] leftHashMap 记录了所有历史位置不在当前窗口内的旧位置不应触发跳转 同类题推荐题目难度一句话思路LeetCode 340: 最多 K 个不同字符的最长子串Medium把约束从无重复改成最多 K 种用 Counter 计数LeetCode 76: 最小覆盖子串Hard用 Counter need/have 匹配收缩窗口找最小LeetCode 424: 替换后的最长重复字符Medium窗口内维护最多字符的频次用总长 - 最多频次 ≤ K 判断来源说明✅ 已验证LeetCode 3 官方题解 AI 实测 文档/论文《算法导论》滑动窗口章节