当前位置：首页 > news >正文

猜猜 AI 写“最长无重复子串“会犯什么错？第一版差点 O(n³)

news 2026/6/1 11:56:26

读完本文你将了解：无重复字符最长子串的核心解法 | AI 从暴力到 HashMap 跳转的演进 | 滑动窗口面试必问的三个坑

📋 题目

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

项目	说明
输入	s = “abcabcbb”
输出	3（子串 “abc”）
约束	0 ≤ s.length ≤ 5 × 10⁴，字符包括英文字母、数字、符号和空格

💡 先问一个问题

把这道题丢给 ChatGPT：“帮我写一个找出最长无重复子串的函数。”

它大概率交出一版暴力解，嵌套循环从头扫到尾。不是 AI 不够聪明——它在还没被纠正之前，走了人类直觉最先想到的那条路。

顺着这条路往下看，AI 是怎么被一步步推到面试通过水平的。

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

# AI 第一版：暴力枚举所有子串deflengthOfLongestSubstring(s:str)->int:n=len(s)max_len=0foriinrange(n):forjinrange(i,n):sub=s[i:j+1]iflen(set(sub))==len(sub):max_len=max(max_len,len(sub))returnmax_len

为什么 AI 会写这个？它把问题拆成了"枚举所有子串 → 检查是否无重复 → 取最长"，这条路径对人来说也是最顺的。问题是：双重循环 O(n²) 本身就是地雷，每次set(sub)又花 O(k)，总体 O(n³)。输入到 5×10⁴ 的时候，这个算法基本跑不完。

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

你可以自己试一下：复制这个代码跑s = "a" * 50000，几分钟都出不来。

🧠 AI 的自我优化

继续跟 AI 对话，它能被推着一步步改：

第 1 次优化：别每次都set(sub)了，用两个指针维护一个窗口，字符进出时动态更新一个 set。这样每次检查重复只要 O(1)，但左指针还是每次只走一步 → O(n²)
第 2 次优化：左指针别傻傻地逐个移动，用 HashMap 记住每个字符上一次出现的位置，遇到重复直接跳到它后面。判断条件char_index[ch] >= left是关键——只跳过窗口内的重复 → O(n)

从 O(n³) 到 O(n)，削减了两层循环。核心手段不是"换个数据结构"，而是换了一个问题视角：不去找所有子串，而是维护一个不断扩张和收缩的窗口。

最终版代码：

# 最优解：HashMap + 滑动窗口，一次遍历deflengthOfLongestSubstring(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

窗口怎么动的？拿 “abcabcbb” 跑一遍：

一句话记住：right 只管往前走，left 在碰到窗口内的老面孔时，跳到它上一次出现的后面。

☕ Java 实现（CSDN 第一大语言必须覆盖）

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;}

Python 写得再溜，面试官问 Java 你要能直接撸出来。两版代码放一起，语法差异一目了然。

🔍 算法模式拆解

这题归到滑动窗口（Sliding Window）模式。判别标准：

特征	本题表现
连续子数组/子串	✅ 连续子串
存在"满足某条件"的区间	✅ 子串内无重复
边界随条件动态变化	✅ left 遇重复就收缩
求最大/最小长度	✅ 求最大长度

滑动窗口的通用骨架：

# 滑动窗口通用模板left=0window_state={}result=0forrightinrange(len(arr)):update_window_state(arr[right])# 1. 扩张whilenotvalid(window_state):# 2. 收缩remove_from_window(arr[left])left+=1result=max(result,right-left+1)# 3. 更新

还有一个细节：本题不需要while——每次最多跳一次就够了。但换成「最小覆盖子串」，while 就是必须的。模板要活学活用，别死记。

🏗️ 真实产品场景

滑动窗口在工程里到处都在用：

Slack 消息去重：排查机器人刷屏时，要找出一段连续消息里最长的不含重复内容的序列。窗口就是那段时间线上的消息。

抖音推荐去重：连续 N 条推荐不能有同一个创作者。每次往队列里塞新视频，如果创作者已经在窗口内出现过，就从左边弹出。每次弹出后重新判断窗口是否达标。

数据库连接池：如果一个连接 ID 已经存在且未归还，新请求要么等要么换一个。窗口维护的就是"当前活跃连接"的集合。

这些东西的内核都一样：一个新元素来了，检查它在不在窗口内，在就收缩，不在就扩张，每次更新结果。

✅ 面试官的点评

你面试写这题，有三层递进：

及格线（能通过）：HashMap 解法写出来，O(n) 时间，能解释 left 跳到char_index[ch] + 1而不是left + 1的原因。这个细节区分了背模板和真理解。

加分项（面评好看）：主动说"如果是 ASCII 字符集，一个 128 长度的 int 数组就够，比 HashMap 快"。

# 加分：int 数组替代 HashMapdeflengthOfLongestSubstring(s:str)->int:last=[-1]*128left=max_len=0forright,chinenumerate(s):idx=ord(ch)iflast[idx]>=left:left=last[idx]+1last[idx]=right max_len=max(max_len,right-left+1)returnmax_len