LeetCode 第 3 题：「无重复字符的最长子串」

字数 5033 2025-10-25 17:11:36

好的，这次我们来讲解 LeetCode 第 3 题：「无重复字符的最长子串」。

这道题是字符串领域中非常经典的一道题，它考察的核心是 “滑动窗口” 思想。我会从题目描述开始，一步步带你分析，并最终给出清晰、高效的解法。

第一步：题目描述

题目链接： 3. Longest Substring Without Repeating Characters

题目要求：
给定一个字符串 s，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1：
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2：
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3：
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是子串的长度，"pwke" 是一个子序列，而不是一个子串。

关键点：

子串：必须是原字符串中连续的字符序列。
无重复字符：子串中的所有字符都是唯一的。
目标是找到最长的那一个，并返回其长度。

第二步：理解问题与暴力解法思路

我们先从最直观的想法开始。

目标： 找出所有不重复的子串，然后比较它们的长度，取最大值。

暴力解法思路：

枚举字符串中所有可能的子串。对于一个长度为 n 的字符串，子串的数量级是 O(n²)。
对于每一个子串，检查它内部是否有重复的字符。我们可以用一个集合（Set）来辅助判断，遍历子串的每个字符，如果字符已经在集合中，说明有重复；否则将其加入集合。
如果没有重复，就记录下这个子串的长度，并与当前已知的最大长度进行比较更新。

暴力解法的问题：
时间复杂度太高，为 O(n³)（枚举子串 O(n²)，检查重复 O(n)）。当字符串很长时（比如 n=10000），计算量会非常大，会超时。

我们需要一个更高效的方法。

第三步：引入“滑动窗口”思想

我们来优化暴力解法。核心观察是：暴力解法有很多不必要的重复检查。

举个例子： 字符串 s = "abcabcbb"。

假设我们已经检查了子串 "abc"，它是无重复的。
接下来检查子串 "abca"，我们发现它在末尾加入了字符 'a'，导致重复。
在暴力解法中，我们接下来可能会去检查 "bcab" 等。
但一个聪明的想法是：当我们发现 "abca" 重复时，重复的字符是 'a'（在位置 0 和位置 3）。那么，包含这两个 'a' 的子串肯定都是无效的。我们能否直接跳过一些检查，从第一个 'a' 之后开始新的查找？

这就是 滑动窗口 的由来。

滑动窗口定义：

我们可以用两个指针（或索引）left 和 right 来表示当前考察的子串的左右边界，即 s[left...right]。
这个由 left 和 right 界定的范围就像一个可以伸缩的“窗口”。
我们保证窗口内的子串始终是 无重复字符 的。
目标是找到所有满足条件的窗口中，right - left + 1（窗口长度）最大的那个。

第四步：滑动窗口的详细步骤

我们一步步模拟滑动窗口的工作过程，以 s = "abcabcbb" 为例。

我们需要一个数据结构来快速判断字符是否在当前窗口内重复出现。哈希集合（HashSet） 是一个完美选择，它可以在 O(1) 时间复杂度内完成查找和插入。

算法流程：

初始化：
- 定义两个指针 left = 0，right = 0。它们都从字符串开头开始。
- 定义一个哈希集合 window_set，用于存储当前窗口中的所有字符。
- 定义一个变量 max_length = 0，用于记录遇到的最大窗口长度。

开始滑动（外层循环，移动右指针 right）：

我们让右指针 right 从 0 开始，逐步向右遍历，每次将一个新的字符纳入窗口。

步骤	right	当前字符	窗口 `s[left...right]`	window_set 内容	是否重复？	操作	max_length
1	0	‘a’	“a”	{ a }	否	将 ‘a’ 加入集合	max(0, 0-0+1)=1
2	1	‘b’	“ab”	{a, b}	否	将 ‘b’ 加入集合	max(1, 1-0+1)=2
3	2	‘c’	“abc”	{a, b, c}	否	将 ‘c’ 加入集合	max(2, 2-0+1)=3
4	3	‘a’	“abca”	{a, b, c}	是（‘a’ 已存在）	关键步骤！

处理重复（内层循环，移动左指针 left）：
- 当发现当前 right 指针指向的字符（例如步骤4中的 'a'）已经在 window_set 中时，意味着窗口内出现了重复。
- 此时，我们不能简单地只移除重复的字符，因为重复的字符可能在窗口的任意位置。正确的做法是：不断从左边界移除字符（移动 left 指针），直到那个引起重复的字符被移出窗口为止。
- 在步骤4中，重复的字符是 'a'，它位于当前窗口的 left（索引0）位置。
  - 我们从集合中移除 s[left]（即移除索引0的 'a'）。
  - 然后将 left 指针向右移动一位（left 从 0 变为 1）。
  - 现在窗口变成了 "bca"。集合中也移除了 'a'。此时再检查，新字符 'a'（索引3）不在集合中了，重复被消除。
- 重点： 内层 while 循环的条件是 “当 s[right] 在集合中”，循环体内不断将 s[left] 从集合中移除，并右移 left。
继续滑动：
- 在解决了重复问题后，将当前 right 的字符（'a'）正式加入集合。
- 然后更新最大长度。此时窗口是 "bca"，长度为 3，与之前的最大值 3 相同。
- 然后 right 继续向右移动，重复上述过程。

后续关键步骤模拟：

right=4，字符 ’b‘：加入后窗口为 ”bcab“，重复（’b‘ 在索引1和4）。进入内层循环：移除 s[left=1]（’b‘），left 变为2。窗口变为 ”cab“，无重复。加入 ‘b’，更新长度（3-2+1=2，最大值仍为3）。
right=5，字符 ’c‘：加入后窗口为 ”cabc“，重复（’c‘ 在索引2和5）。内层循环：移除 s[left=2]（’c‘），left 变为3。窗口变为 ”abc“，无重复。加入 ‘c’，长度仍为3。
right=6，字符 ’b‘：加入后窗口为 ”abcb“，重复（’b‘ 在索引4和6）。内层循环：移除 s[left=3]（’a‘），left 变为4（此时集合为 {b, c}，’b‘ 仍在？不对，这里有个细节！）。

一个重要优化：哈希映射记录索引
在上面的步骤中，当遇到重复字符 ‘b’ 时，我们只能一点点移动 left 指针。如果我们能直接知道重复字符上一次出现的位置，就可以把 left 直接跳到那个位置的下一位。

我们可以用 哈希映射（HashMap） 来代替集合，key 是字符，value 是该字符最新出现的位置索引。

第五步：优化后的滑动窗口（最终方案）

数据结构：

使用一个哈希映射 char_index_map。
两个指针 left 和 right。
变量 max_length。

算法步骤：

left = 0, max_length = 0。
遍历字符串，right 从 0 到 n-1：
a. 检查当前字符 s[right] 是否在 char_index_map 中，并且其存储的索引值大于等于当前 left（这很重要，确保这个重复字符在当前窗口内）。
b. 如果满足条件，说明找到了重复字符。我们直接更新 left 指针：left = max(left, char_index_map[s[right]] + 1)。这里取 max 是为了防止 left 回退（因为 char_index_map 中可能记录着窗口外的旧索引）。
c. 更新 char_index_map[s[right]] = right，记录当前字符的最新位置。
d. 计算当前窗口长度 current_length = right - left + 1，并更新 max_length = max(max_length, current_length)。

以 s = "abcabcbb" 模拟优化后的过程：

right	字符	char_index_map (更新前)	条件判断 (索引 >= left?)	left 更新	更新后 map	窗口	当前长度	max_length
0	‘a’	{}	不在	-	{a:0}	“a”	1	1
1	‘b’	{a:0}	不在	-	{a:0, b:1}	“ab”	2	2
2	‘c’	{a:0, b:1}	不在	-	{a:0, b:1, c:2}	“abc”	3	3
3	‘a’	{a:0, b:1, c:2}	在 (0>=0)	left=0+1=1	{a:3, b:1, c:2}	“bca”	3	3
4	‘b’	{a:3, b:1, c:2}	在 (1>=1)	left=max(1,1+1)=2	{a:3, b:4, c:2}	“cab”	3	3
5	‘c’	{a:3, b:4, c:2}	在 (2>=2)	left=max(2,2+1)=3	{a:3, b:4, c:5}	“abc”	3	3
6	‘b’	{a:3, b:4, c:5}	在 (4>=3)	left=max(3,4+1)=5	{a:3, b:6, c:5}	“cb”	2	3
7	‘b’	{a:3, b:6, c:5}	在 (6>=5)	left=max(5,6+1)=7	{a:3, b:7, c:5}	“b”	1	3

最终结果为 3。这个过程非常高效，每个字符最多被访问两次（left 和 right 各一次），时间复杂度为 O(n)。

第六步：代码实现（Python）

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        # 哈希映射，存储字符最近一次出现的索引
        char_index_map = {}
        left = 0        # 窗口左边界
        max_length = 0  # 结果

        # 右边界 right 从 0 开始遍历
        for right in range(len(s)):
            current_char = s[right]
            
            # 如果字符已存在且在当前窗口内（其索引 >= left）
            if current_char in char_index_map and char_index_map[current_char] >= left:
                # 直接移动左边界到重复字符的下一个位置
                left = char_index_map[current_char] + 1
            
            # 更新字符的最新索引
            char_index_map[current_char] = right
            
            # 计算当前窗口长度并更新最大值
            current_length = right - left + 1
            if current_length > max_length:
                max_length = current_length

        return max_length

总结

问题核心：在字符串中寻找最长的无重复字符的连续子串。
暴力解法：枚举所有子串并检查，效率低（O(n³)）。
核心思想：滑动窗口。用两个指针表示一个窗口，保证窗口内无重复字符。
优化关键：使用哈希映射记录字符最新索引，当遇到重复字符时，可以立即将窗口左边界跳到合适位置，避免左指针的逐步移动。
时间复杂度：O(n)，只需遍历一次字符串。
空间复杂度：O(min(m, n))，其中 m 是字符集大小（ASCII 码最多 128 或 256）。

希望这个从暴力解法到最终优化的循序渐进讲解能让你彻底理解这道经典的滑动窗口题目！

好的，这次我们来讲解 LeetCode 第 3 题：「无重复字符的最长子串」。这道题是字符串领域中非常经典的一道题，它考察的核心是 “滑动窗口” 思想。我会从题目描述开始，一步步带你分析，并最终给出清晰、高效的解法。第一步：题目描述题目链接： 3. Longest Substring Without Repeating Characters 题目要求：给定一个字符串 s ，请你找出其中不含有重复字符的最长子串的长度。示例 1：输入: s = "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc" ，所以其长度为 3。示例 2：输入: s = "bbbbb" 输出: 1 解释: 因为无重复字符的最长子串是 "b" ，所以其长度为 1。示例 3：输入: s = "pwwkew" 输出: 3 解释: 因为无重复字符的最长子串是 "wke" ，所以其长度为 3。请注意，你的答案必须是子串的长度， "pwke" 是一个子序列，而不是一个子串。关键点：子串：必须是原字符串中连续的字符序列。无重复字符：子串中的所有字符都是唯一的。目标是找到最长的那一个，并返回其长度。第二步：理解问题与暴力解法思路我们先从最直观的想法开始。目标：找出所有不重复的子串，然后比较它们的长度，取最大值。暴力解法思路：枚举字符串中所有可能的子串。对于一个长度为 n 的字符串，子串的数量级是 O(n²) 。对于每一个子串，检查它内部是否有重复的字符。我们可以用一个集合（Set）来辅助判断，遍历子串的每个字符，如果字符已经在集合中，说明有重复；否则将其加入集合。如果没有重复，就记录下这个子串的长度，并与当前已知的最大长度进行比较更新。暴力解法的问题：时间复杂度太高，为 O(n³) （枚举子串 O(n²) ，检查重复 O(n) ）。当字符串很长时（比如 n=10000），计算量会非常大，会超时。我们需要一个更高效的方法。第三步：引入“滑动窗口”思想我们来优化暴力解法。核心观察是：暴力解法有很多不必要的重复检查。举个例子：字符串 s = "abcabcbb" 。假设我们已经检查了子串 "abc" ，它是无重复的。接下来检查子串 "abca" ，我们发现它在末尾加入了字符 'a' ，导致重复。在暴力解法中，我们接下来可能会去检查 "bcab" 等。但一个聪明的想法是：当我们发现 "abca" 重复时，重复的字符是 'a' （在位置 0 和位置 3）。那么，包含这两个 'a' 的子串肯定都是无效的。我们能否直接跳过一些检查，从第一个 'a' 之后开始新的查找？这就是滑动窗口的由来。滑动窗口定义：我们可以用两个指针（或索引） left 和 right 来表示当前考察的子串的左右边界，即 s[left...right] 。这个由 left 和 right 界定的范围就像一个可以伸缩的“窗口”。我们保证窗口内的子串始终是无重复字符的。目标是找到所有满足条件的窗口中， right - left + 1 （窗口长度）最大的那个。第四步：滑动窗口的详细步骤我们一步步模拟滑动窗口的工作过程，以 s = "abcabcbb" 为例。我们需要一个数据结构来快速判断字符是否在当前窗口内重复出现。哈希集合（HashSet）是一个完美选择，它可以在 O(1) 时间复杂度内完成查找和插入。算法流程：初始化：定义两个指针 left = 0 ， right = 0 。它们都从字符串开头开始。定义一个哈希集合 window_set ，用于存储当前窗口中的所有字符。定义一个变量 max_length = 0 ，用于记录遇到的最大窗口长度。开始滑动（外层循环，移动右指针 right ）：我们让右指针 right 从 0 开始，逐步向右遍历，每次将一个新的字符纳入窗口。 | 步骤 | left | right | 当前字符 | 窗口 s[left...right] | window_ set 内容 | 是否重复？ | 操作 | max_ length | | :--- | :--- | :--- | :--- | :--- | :--- | :--- | :--- | :--- | | 1 | 0 | 0 | ‘a’ | “a” | { a } | 否 | 将 ‘a’ 加入集合 | max(0, 0-0+1)=1 | | 2 | 0 | 1 | ‘b’ | “ab” | {a, b} | 否 | 将 ‘b’ 加入集合 | max(1, 1-0+1)=2 | | 3 | 0 | 2 | ‘c’ | “abc” | {a, b, c} | 否 | 将 ‘c’ 加入集合 | max(2, 2-0+1)= 3 | | 4 | 0 | 3 | ‘a’ | “abca” | {a, b, c} | 是（‘a’ 已存在） | 关键步骤！ | | 处理重复（内层循环，移动左指针 left ）：当发现当前 right 指针指向的字符（例如步骤4中的 'a' ）已经在 window_set 中时，意味着窗口内出现了重复。此时，我们不能简单地只移除重复的字符，因为重复的字符可能在窗口的任意位置。正确的做法是：不断从左边界移除字符（移动 left 指针），直到那个引起重复的字符被移出窗口为止。在步骤4中，重复的字符是 'a' ，它位于当前窗口的 left （索引0）位置。我们从集合中移除 s[left] （即移除索引0的 'a' ）。然后将 left 指针向右移动一位（ left 从 0 变为 1）。现在窗口变成了 "bca" 。集合中也移除了 'a' 。此时再检查，新字符 'a' （索引3）不在集合中了，重复被消除。重点：内层 while 循环的条件是 “当 s[right] 在集合中”，循环体内不断将 s[left] 从集合中移除，并右移 left 。继续滑动：在解决了重复问题后，将当前 right 的字符（ 'a' ）正式加入集合。然后更新最大长度。此时窗口是 "bca" ，长度为 3，与之前的最大值 3 相同。然后 right 继续向右移动，重复上述过程。后续关键步骤模拟： right=4 ，字符 ’b‘ ：加入后窗口为 ”bcab“ ，重复（’b‘ 在索引1和4）。进入内层循环：移除 s[left=1] （’b‘）， left 变为2。窗口变为 ”cab“ ，无重复。加入 ‘b’，更新长度（3-2+1=2，最大值仍为3）。 right=5 ，字符 ’c‘ ：加入后窗口为 ”cabc“ ，重复（’c‘ 在索引2和5）。内层循环：移除 s[left=2] （’c‘）， left 变为3。窗口变为 ”abc“ ，无重复。加入 ‘c’，长度仍为3。 right=6 ，字符 ’b‘ ：加入后窗口为 ”abcb“ ，重复（’b‘ 在索引4和6）。内层循环：移除 s[left=3] （’a‘）， left 变为4（此时集合为 {b, c}，’b‘ 仍在？不对，这里有个细节！）。一个重要优化：哈希映射记录索引在上面的步骤中，当遇到重复字符 ‘b’ 时，我们只能一点点移动 left 指针。如果我们能直接知道重复字符上一次出现的位置，就可以把 left 直接跳到那个位置的下一位。我们可以用哈希映射（HashMap）来代替集合， key 是字符， value 是该字符最新出现的位置索引。第五步：优化后的滑动窗口（最终方案）数据结构：使用一个哈希映射 char_index_map 。两个指针 left 和 right 。变量 max_length 。算法步骤： left = 0 , max_length = 0 。遍历字符串， right 从 0 到 n-1 ： a. 检查当前字符 s[right] 是否在 char_index_map 中，并且其存储的索引值大于等于当前 left （这很重要，确保这个重复字符在当前窗口内）。 b. 如果满足条件，说明找到了重复字符。我们直接更新 left 指针： left = max(left, char_index_map[s[right]] + 1) 。这里取 max 是为了防止 left 回退（因为 char_index_map 中可能记录着窗口外的旧索引）。 c. 更新 char_index_map[s[right]] = right ，记录当前字符的最新位置。 d. 计算当前窗口长度 current_length = right - left + 1 ，并更新 max_length = max(max_length, current_length) 。以 s = "abcabcbb" 模拟优化后的过程： | right | 字符 | char_ index_ map (更新前) | 条件判断 (索引 >= left?) | left 更新 | 更新后 map | 窗口 | 当前长度 | max_ length | | :--- | :--- | :--- | :--- | :--- | :--- | :--- | :--- | :--- | | 0 | ‘a’ | {} | 不在 | - | {a:0} | “a” | 1 | 1 | | 1 | ‘b’ | {a:0} | 不在 | - | {a:0, b:1} | “ab” | 2 | 2 | | 2 | ‘c’ | {a:0, b:1} | 不在 | - | {a:0, b:1, c:2} | “abc” | 3 | 3 | | 3 | ‘a’ | {a:0, b:1, c:2} | 在 (0>=0) | left=0+1=1 | {a:3, b:1, c:2} | “bca” | 3 | 3 | | 4 | ‘b’ | {a:3, b:1, c:2} | 在 (1>=1) | left=max(1,1+1)=2 | {a:3, b:4, c:2} | “cab” | 3 | 3 | | 5 | ‘c’ | {a:3, b:4, c:2} | 在 (2>=2) | left=max(2,2+1)=3 | {a:3, b:4, c:5} | “abc” | 3 | 3 | | 6 | ‘b’ | {a:3, b:4, c:5} | 在 (4>=3) | left=max(3,4+1)=5 | {a:3, b:6, c:5} | “cb” | 2 | 3 | | 7 | ‘b’ | {a:3, b:6, c:5} | 在 (6>=5) | left=max(5,6+1)=7 | {a:3, b:7, c:5} | “b” | 1 | 3 | 最终结果为 3 。这个过程非常高效，每个字符最多被访问两次（ left 和 right 各一次），时间复杂度为 O(n) 。第六步：代码实现（Python）总结问题核心：在字符串中寻找最长的无重复字符的连续子串。暴力解法：枚举所有子串并检查，效率低（O(n³)）。核心思想：滑动窗口。用两个指针表示一个窗口，保证窗口内无重复字符。优化关键：使用哈希映射记录字符最新索引，当遇到重复字符时，可以立即将窗口左边界跳到合适位置，避免左指针的逐步移动。时间复杂度：O(n)，只需遍历一次字符串。空间复杂度：O(min(m, n))，其中 m 是字符集大小（ASCII 码最多 128 或 256）。希望这个从暴力解法到最终优化的循序渐进讲解能让你彻底理解这道经典的滑动窗口题目！