AI 刷了 50 次才知道：滑动窗口其实只要两句话

读完本文你将了解LeetCode 3 的核心解法 | AI 的解题思路演进 | 面试中的优化方向 题目原题给定一个字符串s找出其中不含有重复字符的最长子串的长度。项目说明输入s abcabcbb输出3子串 “abc”约束0 ≤ s.length ≤ 5×10⁴字符包含英文字母、数字、符号和空格 先问一个问题让 AI 写这道题第一版大概率是「枚举所有子串逐个检查有没有重复字符」——时间复杂度 O(n³)。为什么 AI 这么写因为这是它从大量 LeetCode 解答中统计出的「最安全模式」先穷举再优化。但人类刷题者看到这道题第一反应往往是「维护一个窗口在字符串上滑动」——O(n)。同一个问题AI 和人的起点差了一个量级。这不是 AI 笨是它没有「模式直觉」。而我们要写的正是把这道题里的模式直觉提炼出来。 第一版AI 的朴素解法暴力枚举deflengthOfLongestSubstring(s:str)-int:max_len0nlen(s)foriinrange(n):forjinrange(i1,n1):subs[i:j]iflen(sub)len(set(sub)):max_lenmax(max_len,len(sub))returnmax_len这段代码的逻辑一目了然枚举所有起点i和终点j取出子串s[i:j]检查字符是否重复。AI 为什么这么写因为它看到的是「所有子串」这个最外层框架——穷举是万能的但也是万恶的。复杂度时间 O(n³)空间 O(1)。n50000 时直接超时。 AI 的自我优化AI 的优化链不是线性的它通常会经历三轮迭代第 1 次优化哈希集去重内层循环里用set做去重判断遇到重复就 break不再枚举到j的末尾。时间降到 O(n²)。第 2 次优化固定左指针把「重复时 break」改成「右指针前进时检查左指针只在发现重复时右移」。这时候 O(n²) 变成了 O(n)——因为左右指针各走一遍。第 3 次优化哈希映射左指针跳跃当遇到重复字符c时左指针不应该一格一格挪而应该直接跳到「上一个c出现的下一位」。这才是真正的 O(n)。暴力枚举O(n³)哈希集去重O(n²)双指针滑动O(n)哈希映射跳跃O(n) 最终版 Python 实现最优版deflengthOfLongestSubstring(s:str)-int:last_seen{}# char - 最近一次出现的下标left0max_len0forright,charinenumerate(s):ifcharinlast_seenandlast_seen[char]left:leftlast_seen[char]1last_seen[char]right max_lenmax(max_len,right-left1)returnmax_len要点拆解last_seen记录每个字符最近出现的下标left只增不减这就是「滑动窗口」的精髓last_seen[char] left这个判断非常关键——只有当重复字符在当前窗口内时才需要移动left复杂度时间 O(n)空间 O(min(m, n))m 为字符集大小本题最多 128。☕ Java 实现思路完全一致补上 CSDN 第一大语言publicintlengthOfLongestSubstring(Strings){MapCharacter,IntegerlastSeennewHashMap();intleft0,maxLen0;for(intright0;rights.length();right){charcs.charAt(right);if(lastSeen.containsKey(c)lastSeen.get(c)left){leftlastSeen.get(c)1;}lastSeen.put(c,right);maxLenMath.max(maxLen,right-left1);}returnmaxLen;} 算法模式拆解这道题属于Sliding Window滑动窗口模式是 leetcode-teacher 20 种模式里的第 2 种。什么时候用滑动窗口在数组/字符串中寻找满足条件的「连续子段」条件可以随着窗口边界移动而「增量更新」而不是重新计算本题模式识别特征目标量是「长度」最值不是枚举结果字符重复是一个可以被「局部修正」的条件——遇到重复就缩窗口不需要从头再来窗口的右边界单调递增左边界也单调递增模式变体这道题的窗口是「大小可变的」。还有另一类「固定大小窗口」如「最长含 k 个 1 的子数组」思路类似但需要额外处理窗口大小约束。️ 真实产品场景GitHub 的「活跃 commit 区间」统计想象你要为 GitHub 写一个功能给定一个仓库每天 commit 数量的时间序列找出「连续活跃commit 数 0且不重复每天只算一次」的最长区间。其实就是把字符串换成 commit 数据把「字符不重复」换成「每天去重计数」——滑动窗口完全适用。Twitter 的 Trending Hashtags在时间窗口内统计高频话题本质也是滑动窗口窗口右移时加入新推文、移除过期推文维护一个频率计数器。当窗口大小固定时就是「固定大小滑动窗口」。✅ 面试官的点评写到什么程度算通过暴力解法 → 基础分但基本不通过哈希集去重 O(n²) → 勉强通过但面试官会追问优化双指针 O(n) → 通过这是标准答案加分细节主动说明last_seen[char] left的判断逻辑很多人会漏掉这个条件给出空间复杂度 O(min(m, n)) 的分析能口述窗口大小变化与最值的同步关系常见踩坑左指针一格一格挪没有用哈希映射实现跳跃忘记了last_seen[char] left这个条件导致窗口左边界被错误后移Java 版中HashMap.get()对 null 的处理用containsKeyget两步更安全 同类题推荐LeetCode 438 找到字符串中所有字母异位词— 固定大小窗口 频次统计LeetCode 76 最小覆盖子串— 可变大小窗口 目标字符集计数本题的进阶版LeetCode 340 至多包含 K 个不同字符的最长子串— 本题的变体窗口约束从「无重复」变为「不同字符数 ≤ K」渲染错误:Mermaid 渲染失败: Parse error on line 10: ...口」直觉来自模式训练 AI-Opt: 哈希映射跳跃优化 Hu ----------------------^ Expecting , -, (), ACTOR, got opt来源说明✅ 已验证LeetCode 官方题解 AI 实测 文档/论文算法导论 第 4 章双指针/滑动窗口思想