最长无重复子串 — 从暴力到滑动窗口，AI 是怎么一步步优化的？

读完本文你将了解：最长无重复子串的 3 种解法演进 | 滑动窗口模式的核心原理 | 面试中的常见变体

📋 题目

原题（LeetCode 3）：给定一个字符串s，找出其中不含重复字符的最长子串的长度。

💡 先问一个问题

第一次给 AI 看这道题，它会怎么写？

大多数人第一反应是遍历所有子串，检查每个子串是否包含重复字符。AI 也一样。不是因为它笨，人的直觉就是这样思考的。

🤖 第一版：AI 的朴素解法（暴力枚举）

deflength_of_longest_substring(s:str)->int:"""暴力枚举所有子串，O(n³)"""n=len(s)max_len=0foriinrange(n):forjinrange(i,n):iflen(set(s[i:j+1]))==j-i+1:max_len=max(max_len,j-i+1)returnmax_len

这个代码能跑，但面试官看了会直接叫停。三层嵌套：外层循环起点 i，内层循环终点 j，set()内部又是一层隐式循环。总复杂度 O(n³)，n=50000 时完全不可用。

复杂度分析：时间 O(n³) 空间 O(min(n, ∣Σ∣))

🧠 AI 的自我优化

第 1 次优化：滑动窗口 O(n²)

AI 很快意识到不需要每次都重建set。改用两个指针维护一个窗口，窗口内保证无重复字符：

deflength_of_longest_substring(s:str)->int:"""滑动窗口 + set，O(2n)"""n=len(s)char_set=set()left=0max_len=0forrightinrange(n):whiles[right]inchar_set:char_set.remove(s[left])left+=1char_set.add(s[right])max_len=max(max_len,right-left+1)returnmax_len

从 O(n³) 降到 O(2n) ≈ O(n)。不再每次从零检查子串，而是让 left 指针追赶 right 指针，保证窗口内始终无重复。但这里有个问题——while 循环中每次只移除 left 指向的字符，如果重复字符在窗口中间而不是左端，需要多次循环才能移除。

第 2 次优化：HashMap 直接跳转 O(n)

真正的最优解是用 HashMap 记录每个字符最近出现的位置，遇到重复时直接跳转 left：

deflength_of_longest_substring(s:str)->int:"""HashMap 记录字符位置，O(n) 一次遍历"""char_index={}left=0max_len=0forright,chinenumerate(s):ifchinchar_indexandchar_index[ch]>=left:left=char_index[ch]+1char_index[ch]=right max_len=max(max_len,right-left+1)returnmax_len

从 O(2n) 降到精确 O(n)——left 指针不再一步步挪，而是一次跳到位。这是滑动窗口模式中最核心的技巧：不要用 while 循环逐步收缩窗口，用 HashMap 直接定位跳转点。

☕ Java 实现（思路完全一致）

publicintlengthOfLongestSubstring(Strings){Map<Character,Integer>charIndex=newHashMap<>();intleft=0;intmaxLen=0;for(intright=0;right<s.length();right++){charch=s.charAt(right);if(charIndex.containsKey(ch)&&charIndex.get(ch)>=left){left=charIndex.get(ch)+1;}charIndex.put(ch,right);maxLen=Math.max(maxLen,right-left+1);}returnmaxLen;}

为什么要加 Java？CSDN 第一大用户群体是 Java 开发者。Python 能看懂不代表面试能用 Java 写出来。两版代码摆在一起，读者自己对比，比讲十句话都有用。

🔍 算法模式拆解

这道题是典型的滑动窗口（Sliding Window）模式。

模式识别

滑动窗口解决的是连续子序列/子数组问题，核心特征：

通用模板

defsliding_window(s):"""滑动窗口通用模板"""left=0result=0window={}forright,chinenumerate(s):window[ch]=window.get(ch,0)+1while不满足约束条件:remove window[s[left]]left+=1result=max(result,right-left+1)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] >= left（HashMap 记录了所有历史位置，不在当前窗口内的旧位置不应触发跳转）

📊 同类题推荐

来源说明：

• ✅ 已验证：LeetCode 3 官方题解 + AI 实测
• 📄 文档/论文：《算法导论》滑动窗口章节