滑动窗口算法解析：无重复字符最长子串的O(n)解法

1. 这道题到底在考什么？先看懂题目和边界条件

无重复字符的最长子串是 LeetCode 热题 HOT100 中的经典题目，编号第 3 题。很多人一看到“最长子串”就觉得要暴力枚举所有子串，但这样时间复杂度会直接爆炸。这道题真正考察的是如何在一次遍历中同时记录字符出现位置和动态维护无重复窗口。

先看题目核心要求：给定一个字符串 s，找出其中不含有重复字符的最长子串的长度。注意几个关键边界：

• 子串必须是连续的字符序列，不能跳着选（区别于子序列）
• 空字符串返回 0
• 所有字符包括字母、数字、符号和空格
• 区分大小写（'a' 和 'A' 算不同字符）

示例分析：

• "abcabcbb" → 最长无重复子串是 "abc"，长度 3
• "bbbbb" → 最长就是单个字符 "b"，长度 1
• "pwwkew" → 最长是 "wke"，长度 3（注意 "pwke" 是子序列不是子串）

我一般会先让面试者自己举两个例子，确认他们真的理解“子串”和“无重复”这两个约束条件。很多人栽在把子串和子序列混淆上。

1.1 为什么暴力解法不可行？

最直接的想法是枚举所有可能的子串，检查是否无重复。对于长度为 n 的字符串，子串总数是 O(n²)，每个子串检查无重复需要 O(n)，总时间复杂度 O(n³)。当 n=10000 时，计算量会达到万亿级别，完全不可接受。

即使是优化一点的暴力解法，从每个字符开始向右扩展直到遇到重复字符，时间复杂度也是 O(n²)。对于 LeetCode 的测试用例，n 可能达到 10^5，O(n²) 会超时。

1.2 最优解法的核心思路是什么？

这道题的最优解法是滑动窗口（Sliding Window）配合哈希表记录字符最新位置。核心思想是：

1. 用两个指针 left 和 right 表示当前窗口的左右边界
2. 用哈希表记录每个字符最近出现的位置
3. 当 right 指针向右移动时，如果当前字符已存在且位置在窗口内，就把 left 指针移动到该字符上次出现位置的下一个位置
4. 不断更新最大窗口长度

这样只需要遍历一次字符串，时间复杂度 O(n)，空间复杂度 O(字符集大小)。

2. 滑动窗口解法的详细实现步骤

下面我按实际编码顺序拆解这个解法。先准备基础框架，再逐步加入关键逻辑。

2.1 基础变量定义和初始化

def lengthOfLongestSubstring(s: str) -> int: if not s: # 空字符串特殊情况 return 0 # 记录字符最近出现的位置 char_index = {} left = 0 # 窗口左边界 max_length = 0 # 记录最大长度 # 右指针从 0 开始遍历 for right in range(len(s)): # 核心逻辑在这里逐步添加 pass return max_length

我建议先写好这个框架，特别是处理好空字符串的边界情况。很多人在面试时忘记处理空输入，虽然测试用例可能能过，但会显得不够严谨。

2.2 处理新字符和重复字符的逻辑

def lengthOfLongestSubstring(s: str) -> int: if not s: return 0 char_index = {} left = 0 max_length = 0 for right in range(len(s)): current_char = s[right] # 如果字符已存在且在当前窗口内 if current_char in char_index and char_index[current_char] >= left: # 移动左边界到重复字符的下一个位置 left = char_index[current_char] + 1 # 更新字符的最新位置 char_index[current_char] = right # 计算当前窗口长度 current_length = right - left + 1 max_length = max(max_length, current_length) return max_length

这里最关键的是char_index[current_char] >= left这个判断条件。为什么需要这个条件？因为哈希表记录的是字符历史上最近出现的位置，但这个位置可能不在当前窗口内。比如字符串 "abba"：

• 遍历到最后一个 'a' 时，'a' 在哈希表中的位置是 0
• 但当前 left 已经在 2（因为第二个 'b' 导致 left 移动）
• 此时 0 < 2，说明这个 'a' 不在当前窗口内，不需要移动 left

如果没有这个判断，就会错误地把 left 移回 1，得到错误结果。

2.3 完整可运行代码

def lengthOfLongestSubstring(s: str) -> int: """ 寻找无重复字符的最长子串长度 Args: s: 输入字符串 Returns: int: 最长无重复子串的长度 """ if not s: return 0 # 使用字典记录每个字符最后出现的位置 char_index = {} left = 0 # 滑动窗口左边界 max_length = 0 # 记录最大长度 # 右指针遍历整个字符串 for right in range(len(s)): current_char = s[right] # 如果字符已存在且在当前窗口内（位置 >= left） if current_char in char_index and char_index[current_char] >= left: # 移动左边界到重复字符下一次出现的位置 left = char_index[current_char] + 1 # 更新字符位置记录 char_index[current_char] = right # 计算当前窗口长度并更新最大值 current_length = right - left + 1 if current_length > max_length: max_length = current_length return max_length

这个版本加了详细的注释，实际面试时可以边写边解释关键逻辑。

3. 逐行代码解析和调试技巧

现在我们来逐行分析为什么这样写，以及如何验证代码正确性。

3.1 关键变量作用分析

char_index 字典：

• key：字符
• value：该字符最近一次出现的索引位置
• 作用：快速判断字符是否重复，以及重复字符的位置

left 指针：

• 表示当前无重复子串的起始位置
• 只有当遇到重复字符且该字符在当前窗口内时才会移动
• 保证 left 到 right 之间的子串始终无重复字符

right 指针：

• 遍历字符串的每个位置
• 表示当前无重复子串的结束位置

max_length：

• 动态记录遇到的最大窗口长度
• 每次右指针移动后都更新

3.2 手动模拟执行过程

以 "pwwkew" 为例，一步步跟踪变量变化：

步骤 | right | char | char_index | left | 当前窗口 | max_length -----|-------|------|---------------|------|----------|----------- 0 | 0 | 'p' | {'p':0} | 0 | "p" | 1 1 | 1 | 'w' | {'p':0,'w':1} | 0 | "pw" | 2 2 | 2 | 'w' | {'p':0,'w':2} | 2 | "w" | 2 3 | 3 | 'k' | {'p':0,'w':2,'k':3} | 2 | "wk" | 2 4 | 4 | 'e' | {...,'e':4} | 2 | "wke" | 3 5 | 5 | 'w' | {...,'w':5} | 3 | "kew" | 3

重点看第 2 步：遇到第二个 'w' 时，发现 'w' 已存在且位置 1 >= left(0)，所以把 left 移动到 2。这就是滑动窗口的精髓——遇到重复时不是重头开始，而是跳过重复字符。

3.3 常见错误和调试方法

错误1：忘记检查字符是否在当前窗口内

# 错误写法 if current_char in char_index: # 缺少位置检查 left = char_index[current_char] + 1

这会导致对于 "abba" 这样的输入得到错误结果。调试时可以用这个字符串测试。

错误2：更新 max_length 的位置不对

# 错误写法：在更新 left 之前计算长度 current_length = right - left + 1 if current_char in char_index and char_index[current_char] >= left: left = char_index[current_char] + 1 max_length = max(max_length, current_length)

这样计算的是移动前的窗口长度，可能包含重复字符。一定要在移动 left 之后计算当前窗口长度。

调试技巧：

1. 打印每个循环的关键变量：print(f"right={right}, char={s[right]}, left={left}, window={s[left:right+1]}")
2. 用简单用例手动验证：""（空串）、"a"（单字符）、"aa"（全重复）、"ab"（无重复）
3. 检查边界情况：字符串很长时的性能，包含各种字符的情况

4. 算法优化和变种问题

掌握了基础解法后，我们来看看如何优化和应对变种问题。

4.1 使用数组替代哈希表的优化

如果字符串只包含 ASCII 字符（128 个），可以用固定大小的数组代替哈希表：

def lengthOfLongestSubstring(s: str) -> int: if not s: return 0 # 用数组记录字符位置，初始化为 -1 char_index = [-1] * 128 left = 0 max_length = 0 for right in range(len(s)): # 获取字符的 ASCII 值作为索引 idx = ord(s[right]) # 如果字符已出现且在当前窗口内 if char_index[idx] != -1 and char_index[idx] >= left: left = char_index[idx] + 1 char_index[idx] = right max_length = max(max_length, right - left + 1) return max_length

这种优化在字符串只包含英文字符时更高效，因为数组访问比哈希表查找更快。

4.2 如果需要返回最长子串本身

有时面试官会要求返回最长子串而不是长度：

def longestSubstring(s: str) -> str: if not s: return "" char_index = {} left = 0 max_length = 0 max_start = 0 # 记录最长子串的起始位置 for right in range(len(s)): current_char = s[right] if current_char in char_index and char_index[current_char] >= left: left = char_index[current_char] + 1 char_index[current_char] = right current_length = right - left + 1 if current_length > max_length: max_length = current_length max_start = left # 更新起始位置 return s[max_start:max_start + max_length]

关键变化是增加了 max_start 来记录最长子串的起始位置，最后直接切片返回。

4.3 处理 Unicode 字符的情况

如果字符串包含 Unicode 字符（比如中文），数组方法就不适用了，还是要用哈希表。但原理完全相同：

def lengthOfLongestSubstring(s: str) -> int: if not s: return 0 char_index = {} left = 0 max_length = 0 for right, char in enumerate(s): if char in char_index and char_index[char] >= left: left = char_index[char] + 1 char_index[char] = right max_length = max(max_length, right - left + 1) return max_length

这里用了enumerate让代码更 Pythonic，但逻辑完全一样。

5. 同类问题对比和解题模板

无重复字符的最长子串是滑动窗口类问题的典型代表。掌握这个模板后，很多类似问题都能解决。

5.1 滑动窗口问题的通用模板

def sliding_window_template(s: str) -> int: # 初始化窗口边界和记录结构 left = 0 window_map = {} # 或其他数据结构 result = 0 for right in range(len(s)): # 1. 将右边界字符加入窗口 current_char = s[right] # 更新窗口状态 # 2. 当窗口不满足条件时，移动左边界 while window_invalid(window_map): # 窗口无效的条件 # 移除左边界字符的影响 left_char = s[left] # 更新窗口状态 left += 1 # 3. 更新结果 result = update_result(result, right - left + 1) return result

对于无重复字符问题，"窗口无效的条件"就是出现重复字符。其他问题可能有不同条件。

5.2 相关 LeetCode 题目

掌握了这个模板后，可以解决这些类似问题：

1. 最长连续递增序列（简单）：窗口内要求递增
2. 长度最小的子数组（中等）：窗口内和 ≥ target
3. 替换后的最长重复字符（中等）：窗口内最多替换 k 个字符
4. 字符串的排列（中等）：窗口包含特定字符组合

5.3 面试常见追问问题

面试官可能会基于这个题目追问：

Q: 时间复杂度和空间复杂度是多少？A: 时间复杂度 O(n)，每个字符最多被访问两次（左右指针各一次）。空间复杂度 O(min(m, n))，其中 m 是字符集大小。

Q: 为什么这是最优解法？A: 因为必须至少遍历一次字符串来检查每个字符，O(n) 是理论下界。我们的解法达到了这个下界。

Q: 如果字符串特别大，有什么优化思路？A: 算法本身已经最优，但可以优化数据结构。如果字符集已知且较小，用数组代替哈希表。如果内存紧张，可以考虑分批处理，但滑动窗口本身需要随机访问，分批比较困难。

6. 实战练习和避坑指南

最后给一些实战建议，帮助你在真正编码时避免常见陷阱。

6.1 自测用例清单

写完代码后，用这些用例测试：

test_cases = [ ("", 0), # 空字符串 ("a", 1), # 单字符 ("aa", 1), # 全重复 ("ab", 2), # 无重复 ("abcabcbb", 3), # 标准用例1 ("bbbbb", 1), # 标准用例2 ("pwwkew", 3), # 标准用例3 ("abba", 2), # 回文型重复 ("dvdf", 3), # 中间重复 ("tmmzuxt", 5), # 复杂重复模式 ]

特别是 "abba" 和 "tmmzuxt" 这种，能检验是否正确处理了历史重复不在当前窗口的情况。

6.2 编码时容易忽略的细节

1. 输入验证：先处理空字符串情况
2. 变量命名：使用有意义的变量名，如 char_index 而不是简单的 map
3. 边界检查：确保索引不越界，特别是 left = char_index[char] + 1
4. 更新顺序：先处理重复字符移动 left，再更新字符位置，最后计算长度
5. 返回值：确保所有分支都有返回值

6.3 性能优化考虑

虽然时间复杂度已经是 O(n)，但在实际面试中还可以展示优化意识：

• 如果字符串很长，考虑使用更紧凑的数据结构
• 如果字符集已知，提前分配固定大小数组
• 如果只需要判断是否超过某个长度，可以提前终止

我一般建议先写出清晰正确的版本，如果时间允许再讨论优化。不要为了微小的优化让代码变得难以理解。

这道题的核心价值在于理解滑动窗口的思想和哈希表的配合使用。真正掌握后，你会发现很多字符串处理问题都能用类似的思路解决。重点不是背代码，而是理解为什么这样设计窗口的移动规则。