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

字数 2337 2025-10-25 17:33:22

好的，我们这次来详细学习 LeetCode 第 3 题「无重复字符的最长子串」。

1. 题目描述

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

示例：

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

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

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

注意：子串是连续的，子序列可以不连续。

2. 题意理解

我们要找的是 连续的一段字符，并且里面不能有重复的字符。
比如 "abcabcbb"：

从下标 0 开始："a" → "ab" → "abc" 都无重复，长度 3。
如果继续加 'a'，就重复了，所以不能直接延长，需要调整起点。

关键：当发现重复字符时，我们要跳过重复字符出现的位置，重新计算无重复区间。

3. 思路演进

3.1 暴力法（用于理解问题）

枚举所有子串（起点 i，终点 j），检查是否无重复字符。
检查重复可以用哈希集合。
时间复杂度：O(n³) 或 O(n²)（取决于检查重复的方式），会超时。

3.2 滑动窗口（双指针）思路

我们维护一个窗口 [left, right]，表示当前考察的子串。

用哈希集合 windowSet 存储窗口内的字符（为了 O(1) 判断重复）。
right 指针逐个向右移动，将字符加入窗口：
- 如果 s[right] 不在集合中，说明无重复，更新最大长度。
- 如果 s[right] 已在集合中，说明出现重复，需要移动 left 指针，从集合中移除 s[left]，left++，直到重复字符被移出窗口为止，然后才把 s[right] 加入集合。

示例 s = "abcabcbb"：

初始：left=0, right=0, 集合 {}, maxLen=0
right=0: 'a' 不在集合 → 加入，maxLen=1
right=1: 'b' 不在集合 → 加入，maxLen=2
right=2: 'c' 不在集合 → 加入，maxLen=3
right=3: 'a' 在集合中（此时集合 {a,b,c}）→ 移动 left：
- 移除 s[0]='a'，left=1，集合 {b,c}
- 现在 'a' 不在集合了，加入 'a'，maxLen 仍为 3
依此类推。

这样每个字符最多进入和离开集合一次，时间复杂度 O(n)。

3.3 优化：直接跳转 left

上面在发现重复时，left 是一个个移动的，其实可以一次跳到重复字符的下一个位置。

方法：用哈希映射 lastOccurrence 记录每个字符 最近一次出现的下标。

当 s[right] 在 lastOccurrence 中且其索引 ≥ left（即在当前窗口内重复），则直接把 left 设为 lastOccurrence[s[right]] + 1。
更新 lastOccurrence[s[right]] = right。

这样避免了一步步移动 left。

4. 详细步骤（优化后滑动窗口）

初始化：
- left = 0
- maxLen = 0
- 哈希表 map：字符 → 最后出现的位置
遍历 right 从 0 到 n-1：
- 如果当前字符 ch = s[right] 在 map 中，并且 map[ch] >= left（在当前窗口内重复）：
  - 将 left 更新为 map[ch] + 1（跳过重复字符上次出现的位置）
- 更新 maxLen = max(maxLen, right - left + 1)
- 更新 map[ch] = right
返回 maxLen

5. 示例推演（s = "abcabcbb"）

right	ch	map 初始(空)	left	动作	maxLen
0	a	存 a:0	0	无重复，max=1	1
1	b	存 b:1	0	无重复，max=2	2
2	c	存 c:2	0	无重复，max=3	3
3	a	a 在 map 中 index=0 ≥ left=0 → 重复	left=0+1=1	更新 a:3，max=3? right-left+1=3-1+1=3	3
4	b	b 在 map 中 index=1 ≥ left=1 → 重复	left=1+1=2	更新 b:4，长度=4-2+1=3	3
5	c	c 在 map 中 index=2 ≥ left=2 → 重复	left=2+1=3	更新 c:5，长度=5-3+1=3	3
6	b	b 在 map 中 index=4 ≥ left=3 → 重复	left=4+1=5	更新 b:6，长度=6-5+1=2	3
7	b	b 在 map 中 index=6 ≥ left=5 → 重复	left=6+1=7	更新 b:7，长度=7-7+1=1	3

最终结果：3。

6. 代码实现（Python）

def lengthOfLongestSubstring(s: str) -> int:
    char_map = {}  # 存储字符最后出现的索引
    left = 0
    max_len = 0
    
    for right, ch in enumerate(s):
        if ch in char_map and char_map[ch] >= left:
            left = char_map[ch] + 1
        max_len = max(max_len, right - left + 1)
        char_map[ch] = right
    
    return max_len

7. 复杂度分析

时间复杂度：O(n)，n 为字符串长度，每个字符遍历一次。
空间复杂度：O(min(m, n))，m 为字符集大小（ASCII 最多 128），哈希表存储字符索引。

这样一步步从暴力法到滑动窗口，再到优化跳转，应该能让你彻底理解这个经典题目了。需要我再解释某一部分吗？

好的，我们这次来详细学习 LeetCode 第 3 题「无重复字符的最长子串」。 1. 题目描述题目：给定一个字符串 s ，请你找出其中不含有重复字符的最长子串的长度。示例：注意：子串是连续的，子序列可以不连续。 2. 题意理解我们要找的是连续的一段字符，并且里面不能有重复的字符。比如 "abcabcbb" ：从下标 0 开始： "a" → "ab" → "abc" 都无重复，长度 3。如果继续加 'a' ，就重复了，所以不能直接延长，需要调整起点。关键：当发现重复字符时，我们要跳过重复字符出现的位置，重新计算无重复区间。 3. 思路演进 3.1 暴力法（用于理解问题）枚举所有子串（起点 i ，终点 j ），检查是否无重复字符。检查重复可以用哈希集合。时间复杂度：O(n³) 或 O(n²)（取决于检查重复的方式），会超时。 3.2 滑动窗口（双指针）思路我们维护一个窗口 [left, right] ，表示当前考察的子串。用哈希集合 windowSet 存储窗口内的字符（为了 O(1) 判断重复）。 right 指针逐个向右移动，将字符加入窗口：如果 s[right] 不在集合中，说明无重复，更新最大长度。如果 s[right] 已在集合中，说明出现重复，需要移动 left 指针，从集合中移除 s[left] ， left++ ，直到重复字符被移出窗口为止，然后才把 s[right] 加入集合。示例 s = "abcabcbb" ：初始： left=0, right=0 , 集合 {} , maxLen=0 right=0: 'a' 不在集合 → 加入，maxLen=1 right=1: 'b' 不在集合 → 加入，maxLen=2 right=2: 'c' 不在集合 → 加入，maxLen=3 right=3: 'a' 在集合中（此时集合 {a,b,c} ）→ 移动 left：移除 s[ 0]='a'，left=1，集合 {b,c} 现在 'a' 不在集合了，加入 'a' ，maxLen 仍为 3 依此类推。这样每个字符最多进入和离开集合一次，时间复杂度 O(n)。 3.3 优化：直接跳转 left 上面在发现重复时， left 是一个个移动的，其实可以一次跳到重复字符的下一个位置。方法：用哈希映射 lastOccurrence 记录每个字符最近一次出现的下标。当 s[right] 在 lastOccurrence 中且其索引 ≥ left （即在当前窗口内重复），则直接把 left 设为 lastOccurrence[s[right]] + 1 。更新 lastOccurrence[s[right]] = right 。这样避免了一步步移动 left 。 4. 详细步骤（优化后滑动窗口）初始化： left = 0 maxLen = 0 哈希表 map ：字符 → 最后出现的位置遍历 right 从 0 到 n-1：如果当前字符 ch = s[right] 在 map 中，并且 map[ch] >= left （在当前窗口内重复）：将 left 更新为 map[ch] + 1 （跳过重复字符上次出现的位置）更新 maxLen = max(maxLen, right - left + 1) 更新 map[ch] = right 返回 maxLen 5. 示例推演（s = "abcabcbb"） | right | ch | map 初始(空) | left | 动作 | maxLen | |-------|----|--------------|------|------|--------| | 0 | a | 存 a:0 | 0 | 无重复，max=1 | 1 | | 1 | b | 存 b:1 | 0 | 无重复，max=2 | 2 | | 2 | c | 存 c:2 | 0 | 无重复，max=3 | 3 | | 3 | a | a 在 map 中 index=0 ≥ left=0 → 重复 | left=0+1=1 | 更新 a:3，max=3? right-left+1=3-1+1=3 | 3 | | 4 | b | b 在 map 中 index=1 ≥ left=1 → 重复 | left=1+1=2 | 更新 b:4，长度=4-2+1=3 | 3 | | 5 | c | c 在 map 中 index=2 ≥ left=2 → 重复 | left=2+1=3 | 更新 c:5，长度=5-3+1=3 | 3 | | 6 | b | b 在 map 中 index=4 ≥ left=3 → 重复 | left=4+1=5 | 更新 b:6，长度=6-5+1=2 | 3 | | 7 | b | b 在 map 中 index=6 ≥ left=5 → 重复 | left=6+1=7 | 更新 b:7，长度=7-7+1=1 | 3 | 最终结果：3。 6. 代码实现（Python） 7. 复杂度分析时间复杂度：O(n)，n 为字符串长度，每个字符遍历一次。空间复杂度：O(min(m, n))，m 为字符集大小（ASCII 最多 128），哈希表存储字符索引。这样一步步从暴力法到滑动窗口，再到优化跳转，应该能让你彻底理解这个经典题目了。需要我再解释某一部分吗？