高频必考！无重复最长子串：滑动窗口为什么是 O(n) 而非 O(n²)？

LeetCode 3「无重复字符的最长子串」「国内大厂面试命中率 TOP 5」。但很多人写出来的代码要么超时要么边界错要么自己都说不清为什么能 O(n)。今天我不只给你“能 AC 的代码”更给你一套「“同向双指针 哈希表定位”」的通用框架。以后遇到“子串”类问题你都能用同样的套路——「右扩左缩窗口内保持合法状态」。 题目速览30 秒读懂给定字符串s找出「不含有重复字符」的「最长子串」的长度。「示例」输入: abcabcbb → 输出 3子串 abc 输入: bbbbb → 输出 1子串 b 输入: pwwkew → 输出 3子串 wke注意不是 pwke 因为它不连续「约束」长度0~5×10⁴字符集很大字母数字符号空格—— 暴力法必挂。 核心思路从“三层循环”到“一次遍历”暴力在哪儿foriinrange(n):forjinrange(i, n):if子串 s[i:j1] 无重复:更新最大长度O(n³)n50000 时直接爆炸。如何优化——复用已有信息「关键观察」如果当前窗口[left, right]内无重复那么当right右移一位时「只需要检查新字符是否在窗口内出现过」。若没出现过 → 窗口直接扩展长度 1若出现过 → 不必回退right只需「将left跳到重复字符的下一个位置」窗口依然合法。这就是滑动窗口的精髓「两个指针都只向前移动」每个字符最多被访问两次一次进窗口一次出窗口所以总时间 O(n)。️ 图解全过程手把手走一遍以s abcabcbb为例步骤右指针 R当前字符窗口内容左指针 L是否重复动作最大长度10a{a}0否扩展窗口121b{a,b}0否扩展窗口232c{a,b,c}0否扩展窗口343a{a,b,c,「a」}0✅ a 重复L 跳到 011354b{b,c,a,「b」}1✅ b 重复L 跳到 112365c{c,a,b,「c」}2✅ c 重复L 跳到 213376b{a,b,c,「b」}3✅ b 重复L 跳到 415387b{c,b,「b」}5✅ b 重复L 跳到 6173最终最大长度为「3」窗口为 abc 或 bca 等正确 ✅注意观察right从未回退left也只向右跳跃两指针总移动次数 ≤ 2n。 代码实现Python JavaPython 版推荐写法classSolution:deflengthOfLongestSubstring(self, s: str)- int:last_pos {}# 字符 → 最近一次出现的下标left 0max_len 0forright, chinenumerate(s):# 如果 ch 已经在当前窗口内last_pos[ch] leftifchinlast_posandlast_pos[ch] left:left last_pos[ch] 1# 直接跳到重复字符的下一位last_pos[ch] right# 更新最新位置max_len max(max_len, right - left 1)returnmax_lenJava 版classSolution{publicintlengthOfLongestSubstring(String s){MapCharacter, Integer lastPos newHashMap();intleft 0, maxLen 0;for(intright 0; right s.length(); right) {charch s.charAt(right);if(lastPos.containsKey(ch) lastPos.get(ch) left) {left lastPos.get(ch) 1;}lastPos.put(ch, right);maxLen Math.max(maxLen, right - left 1);}returnmaxLen;}}⚠️「致命坑」判断重复时「必须」加上 left因为字符可能早在left左边出现过但早已被排除在窗口外此时不该收缩左指针。漏掉这个条件代码会出错比如tmmzuxt会返回错误长度。⏱️ 复杂度分析面试必问「时间复杂度O(n)」右指针遍历一次 O(n)左指针最多也移动 n 次只增不减哈希表操作 O(1)总计 O(n)。「空间复杂度O(min(m, n))」m 为字符集大小如 ASCII 128Unicode 很大。当字符集有限时如小写字母 26 个可视为「O(1)」额外空间。 举一反三4 道高频变种题一套框架通吃题目差异点应对策略「LeetCode 209. 长度最小的子数组」求和 ≥ target 的最短连续子数组窗口内维护元素和右扩满足条件时收缩左边界并更新最小长度「LeetCode 904. 水果成篮」最多包含 2 种字符的最长子串哈希表计数种类 2 时 left 右移直到种类 ≤ 2「LeetCode 76. 最小覆盖子串」包含目标串所有字符的最小子串维护 needs 和 window用 match 变量记录匹配状态满足时收缩 left 并更新答案「LeetCode 438. 找到字符串中所有字母异位词」固定窗口大小等于 p 的长度窗口大小固定每次左右同步滑动比较字符频率数组是否相等 面试追问模拟提前准备惊艳全场「Q1滑动窗口有两种写法一种是用哈希表直接跳另一种是用集合逐个移除有什么区别」直接跳本题性能更好因为 left 可以一次性跳到重复位置1而集合方式必须每次 left 并移除一个字符直到没有重复。两者都是 O(n)但常数不同。面试时推荐直接跳写法更体现对数据结构的掌握。「Q2如果字符集只有 26 个小写字母怎么优化空间」用一个长度为 26 的 int 数组记录每个字符的最新位置lastPos[ch - a] right空间 O(1) 且访问更快。「Q3如果题目改为“最长无重复子序列”不要求连续答案会怎样」那答案就是所有不同字符的个数比如 “abcabcbb” 的不同字符是 a,b,c答案为 3问题退化为“统计不同字符数量”与滑动窗口无关。所以连续性是本题的难点所在。 实战小技巧刷题党必备「口诀」右指针探路左指针清障哈希表记位置窗口长度随时算。「模板」凡是“最长/最短子串子数组”且满足某种条件优先考虑滑动窗口。「边界」空字符串返回 0左指针跳跃时保证left right 1不会越界。 实际应用场景不止是刷题「TCP 滑动窗口协议」拥塞控制中窗口大小动态调整保证不丢包。「文本去重检测」在编辑器中实时高亮重复输入的字符。「日志分析」统计某时间窗口内不重复的 IP 访问量。「基因序列分析」在 DNA 序列中找最长不含特定碱基的子串。