无重复字符的最长子串 — AI 写了两版，暴力解被面试官一句话怼回来了

读完本文你将了解：滑动窗口的直觉推导 | AI 从暴力到优化的完整演进 | 面试中的细节加分项

📋 题目

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

💡 先问一个问题

如果让 ChatGPT 第一次写这道题，它会怎么写？

我实测了一下。它第一反应居然是——三层循环。

deflength_of_longest_substring(s:str)->int:max_len=0foriinrange(len(s)):forjinrange(i,len(s)):sub=s[i:j+1]iflen(set(sub))==len(sub):max_len=max(max_len,len(sub))returnmax_len

不能说错，但面试官看到这段代码，表情是这样的 😑

复杂度：时间 O(n³)，空间 O(n)

别笑。这个解法的思路很朴素——枚举所有子串，检查每个子串是否有重复字符。三层循环里，最内层 set(sub) 遍历了子串的每个字符。

人类直觉 ≈ 暴力枚举，这很自然。但面试考的不是"能不能写出来"，而是"能不能意识到问题在哪"。

🤖 AI 的自我优化

第 1 次优化：从 O(n³) 到 O(n²)

AI 看到自己的代码后，第一反应是去掉最内层 set 的重复遍历，用滑动窗口的雏形：

deflength_of_longest_substring(s:str)->int:max_len=0foriinrange(len(s)):seen=set()forjinrange(i,len(s)):ifs[j]inseen:breakseen.add(s[j])max_len=max(max_len,j-i+1)returnmax_len

复杂度：时间 O(n²)，空间 O(min(n, |Σ|))

改进在哪？用set实时跟踪当前窗口的字符，遇到重复就提前 break，而不是每次都生成整个子串再检查。

但面试官依然不满意——“n 最大 5×10⁴，n² 是 2.5×10⁹，超时。”

第 2 次优化：真正的滑动窗口（O(n)）

AI 终于意识到，当右指针发现重复字符时，左指针不用一步步挪，可以直接跳到重复字符的下一个位置。

deflength_of_longest_substring(s:str)->int: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(n)，空间 O(min(n, |Σ|))

关键变化只有一行：left = char_index[ch] + 1。当字符重复时，左指针直接跳到重复字符的下一个位置，而不是像上一步那样 left++ 一步步挪。

☕ Java 实现

publicintlengthOfLongestSubstring(Strings){Map<Character,Integer>charIndex=newHashMap<>();intleft=0,maxLen=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;}

HashMap 替代 dict，containsKey替代in，逻辑完全对称。面试中写出 Java 版，面试官知道你是个能写工程的。

🔍 算法模式拆解

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

什么时候用滑动窗口？

• 处理连续子数组/子串问题
• 需要在一个区间内维护某种约束（无重复、和 ≤ K、至少包含某些字符）
• 右指针拓展窗口，左指针收缩窗口

滑动窗口的通用模板：

defsliding_window(s:str)->int:left=0result=0window={}# 或 set / 计数器forright,chinenumerate(s):# 更新窗口状态update(window,ch)# 不满足条件时收缩左边界whileinvalid(window):remove(window,s[left])left+=1# 更新结果result=max(result,right-left+1)returnresult

模式变体：

• 固定窗口大小：滑动窗口的平均值（LeetCode 643）
• 可变窗口：无重复字符的最长子串（本题）
• 双指针并行：最小覆盖子串（LeetCode 76）

🏗️ 真实产品场景

Slack 的消息会话窗口中，用户可能会在短时间内刷出大量消息。系统需要检测当前视图中的消息序列里，不重复的标签/用户提及是否连续——这直接决定了是否需要提示"你可能错过了 @someone 的回复"。

另一个场景：Twitter 的时间线滑动。用户在滑动时，客户端需要确保 feed 中连续 N 条推文没有重复内容（广告除外）。用滑动窗口算法，客户端可以在 O(n) 时间内扫描整个时间线，标记出需要过滤的重复项。

✅ 面试官的点评

写到什么程度算"通过"：

• 写出 O(n) 的滑动窗口解法 → 通过
• 能解释为什么 O(n²) 版本会超时 → 加分
• 能处理字符集扩展（Unicode/ASCII）→ 加分

常见踩坑点：

• 忘记char_index[ch] >= left判断——当左指针已经越过某个字符的旧位置时，旧索引不应该再影响窗口收缩
• 更新max_len的时机：要在每次右指针移动后更新，而不是只在收缩后更新
• 边界条件：空字符串返回 0

加分细节：

• 讨论字符集规模对空间复杂度的影响（ASCII 128 vs Unicode 1M+）
• 如果输入是字节流（streaming），滑动窗口也可以在线处理

📊 同类题推荐

来源说明：

• ✅ 已验证：LeetCode 官方题解 + AI 实测
• 📄 来源：算法导论（CLRS）第 15 章——动态规划与滑动窗口