读完本文你将了解滑动窗口的直觉推导 | AI 从暴力到优化的完整演进 | 面试中的细节加分项 题目原题给定一个字符串 s找出其中不含有重复字符的最长子串的长度。项目说明输入s “abcabcbb”输出3解释最长无重复子串是 “abc”长度为 3约束0 ≤ s.length ≤ 5×10⁴字符集为 ASCII 先问一个问题如果让 ChatGPT 第一次写这道题它会怎么写我实测了一下。它第一反应居然是——三层循环。deflength_of_longest_substring(s:str)-int:max_len0foriinrange(len(s)):forjinrange(i,len(s)):subs[i:j1]iflen(set(sub))len(sub):max_lenmax(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_len0foriinrange(len(s)):seenset()forjinrange(i,len(s)):ifs[j]inseen:breakseen.add(s[j])max_lenmax(max_len,j-i1)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{}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(n)空间 O(min(n, |Σ|))关键变化只有一行left char_index[ch] 1。当字符重复时左指针直接跳到重复字符的下一个位置而不是像上一步那样 left 一步步挪。暴力枚举O(n³)窗口雏形O(n²)滑动窗口O(n)哈希表优化O(n) 空间☕ Java 实现publicintlengthOfLongestSubstring(Strings){MapCharacter,IntegercharIndexnewHashMap();intleft0,maxLen0;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;}HashMap 替代 dictcontainsKey替代in逻辑完全对称。面试中写出 Java 版面试官知道你是个能写工程的。 算法模式拆解这道题是滑动窗口Sliding Window模式的经典代表。什么时候用滑动窗口处理连续子数组/子串问题需要在一个区间内维护某种约束无重复、和 ≤ K、至少包含某些字符右指针拓展窗口左指针收缩窗口滑动窗口的通用模板defsliding_window(s:str)-int:left0result0window{}# 或 set / 计数器forright,chinenumerate(s):# 更新窗口状态update(window,ch)# 不满足条件时收缩左边界whileinvalid(window):remove(window,s[left])left1# 更新结果resultmax(result,right-left1)returnresult模式变体固定窗口大小滑动窗口的平均值LeetCode 643可变窗口无重复字符的最长子串本题双指针并行最小覆盖子串LeetCode 76是否是否无重复和≤K字符覆盖输入数组/字符串需要连续子区间?窗口大小固定?其他模式固定滑动窗口O(n)可变滑动窗口O(n)需要额外约束?哈希表左右指针前缀和双指针计数器双指针️ 真实产品场景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 76最小覆盖子串Hard两个哈希表滑动窗口找到包含所有目标字符的最短窗口LeetCode 424替换后的最长重复字符Medium滑动窗口频率统计窗口内最多可替换 K 个字符LeetCode 904水果成篮Medium滑动窗口最多两种水果的约束本质是最多两个不同字符的最长子串来源说明✅ 已验证LeetCode 官方题解 AI 实测 来源算法导论CLRS第 15 章——动态规划与滑动窗口
