 而非 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:j+1] 无重复:
更新最大长度
O(n³)，n=50000 时直接爆炸。
如何优化？——复用已有信息
「关键观察：」
如果当前窗口[left, right]内无重复，那么当right右移一位时，「只需要检查新字符是否在窗口内出现过」。
若没出现过 → 窗口直接扩展，长度 +1 若出现过 → 不必回退 right，只需「将left跳到重复字符的下一个位置」，窗口依然合法。
这就是滑动窗口的精髓：「两个指针都只向前移动」，每个字符最多被访问两次（一次进窗口，一次出窗口），所以总时间 O(n)。
🖼️ 图解全过程（手把手走一遍）
以s = "abcabcbb"为例：
| 步骤 | 右指针 R | 当前字符 | 窗口内容 | 左指针 L | 是否重复？ | 动作 | 最大长度 |
|---|---|---|---|---|---|---|---|
| 1 | 0 | a | {a} | 0 | 否 | 扩展窗口 | 1 |
| 2 | 1 | b | {a,b} | 0 | 否 | 扩展窗口 | 2 |
| 3 | 2 | c | {a,b,c} | 0 | 否 | 扩展窗口 | 3 |
| 4 | 3 | a | {a,b,c,「a」} | 0 | ✅ a 重复 | L 跳到 0+1=1 | 3 |
| 5 | 4 | b | {b,c,a,「b」} | 1 | ✅ b 重复 | L 跳到 1+1=2 | 3 |
| 6 | 5 | c | {c,a,b,「c」} | 2 | ✅ c 重复 | L 跳到 2+1=3 | 3 |
| 7 | 6 | b | {a,b,c,「b」} | 3 | ✅ b 重复 | L 跳到 4+1=5 | 3 |
| 8 | 7 | b | {c,b,「b」} | 5 | ✅ b 重复 | L 跳到 6+1=7 | 3 |
最终最大长度为「3」（窗口为 "abc" 或 "bca" 等），正确 ✅
注意观察：
right从未回退，left也只向右跳跃，两指针总移动次数 ≤ 2n。
💻 代码实现（Python + Java）
Python 版（推荐写法）
classSolution:
deflengthOfLongestSubstring(self, s: str)-> int:
last_pos = {}# 字符 → 最近一次出现的下标
left =0
max_len =0
forright, chinenumerate(s):
# 如果 ch 已经在当前窗口内（last_pos[ch] >= left）
ifchinlast_posandlast_pos[ch] >= left:
left = last_pos[ch] +1# 直接跳到重复字符的下一位
last_pos[ch] = right# 更新最新位置
max_len = max(max_len, right - left +1)
returnmax_len
Java 版
classSolution{
publicintlengthOfLongestSubstring(String s){
Map<Character, 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 128，Unicode 很大）。当字符集有限时（如小写字母 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 序列中找最长不含特定碱基的子串。
