210 lines
7.7 KiB
Markdown
210 lines
7.7 KiB
Markdown
---
|
||
tags: ["LeetCode", "滑动窗口", "哈希表", "中等"]
|
||
create time: 2026-05-14 10:00
|
||
---
|
||
|
||
# 08-无重复字符的最长子串
|
||
|
||
## 题面
|
||
|
||
给定一个字符串 `s`，请你找出其中不含有重复字符的 **最长子串** 的长度。
|
||
|
||
**示例 1：**
|
||
|
||
```
|
||
输入: s = "abcabcbb"
|
||
输出: 3
|
||
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
|
||
注意 "bca" 和 "cab" 也是正确答案。
|
||
```
|
||
|
||
**示例 2：**
|
||
|
||
```
|
||
输入: s = "bbbbb"
|
||
输出: 1
|
||
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
|
||
```
|
||
|
||
**示例 3：**
|
||
|
||
```
|
||
输入: s = "pwwkew"
|
||
输出: 3
|
||
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
|
||
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
|
||
```
|
||
|
||
**提示：**
|
||
|
||
- `0 <= s.length <= 5 * 10^4`
|
||
- `s` 由英文字母、数字、符号和空格组成
|
||
|
||
---
|
||
|
||
## 思路
|
||
|
||
> [!question] 💡 思考
|
||
> 子串要求**连续**，这和我们之前做过的"子序列"问题有本质区别——子串可以用窗口框定一段区间来维护约束条件。那么问题就变成：**如何用一个"可伸缩的窗口"来覆盖所有合法的子串？**
|
||
|
||
### 方法一：暴力枚举 ❌
|
||
|
||
枚举所有可能的子串 `(i, j)`，对每个子串检查是否有重复字符。
|
||
|
||
- **时间复杂度：O(n³)** — O(n²) 个子串，每个子串检查 O(n)
|
||
- **空间复杂度：O(min(n, m))** — 用哈希集合存储子串字符（m 为字符集大小）
|
||
|
||
`n ≤ 5 × 10⁴` 时显然不可行，必须寻找更优方案。
|
||
|
||
### 方法二：滑动窗口 + 哈希表 ⭐（最优）
|
||
|
||
> [!info] 🎯 核心思想
|
||
> 维护一个**左右指针定义的窗口** `[left, right]`，表示当前不含重复字符的子串。右指针不断右扩，左指针在遇到重复时右缩。**关键优化：当发现重复字符时，左指针不必每次只走一格，而是直接跳到该字符上次出现位置的下一位。**
|
||
|
||
为什么可以这样跳？因为如果字符 `c` 上一次出现在索引 `lastPos[c]`，当前右指针到了 `right` 且 `c == s[right]`，那么从 `left` 到 `right - 1` 之间只要包含这个 `c`，无论左指针停在 `left+1`、`left+2`、……还是 `lastPos[c]+1`，窗口内都会继续存在重复 —— 只有跨过 `lastPos[c]` 才能消除重复。
|
||
|
||
```mermaid
|
||
flowchart TD
|
||
A["left = 0, right = 0"] --> B{"right < len(s)?"}
|
||
B -->|"否"| G["返回 maxLen"]
|
||
B -->|"是"| C["取当前字符 char"]
|
||
C --> D{"char 出现过且在窗口内?"}
|
||
D -->|"是"| E["left = lastPos[char] + 1"]
|
||
D -->|"否"| F["更新 maxLen"]
|
||
E --> F
|
||
F --> H["lastPos[char] = right"]
|
||
H --> I["right++"]
|
||
I --> B
|
||
```
|
||
|
||
> [!note] 🧠 "在窗口内"的判断
|
||
> 字符 `c` 可能早已出现在字符串中、但已经不在当前窗口里了（左指针已经越过它）。此时不应触发收缩操作。判断条件是：`lastPos[c] >= left`，即该字符的上次出现位置在当前窗口的左边界或之内。
|
||
|
||
以 `s = "pwwkew"` 为例：
|
||
|
||
> [!abstract] 🔍 逐步推演
|
||
|
||
| 步骤 | right | s[right] | lastPos（记录） | 是否重复且在窗口内 | left | maxLen |
|
||
|------|-------|----------|----------------|-------------------|------|--------|
|
||
| 初始 | — | — | `{}` | — | 0 | 0 |
|
||
| 1 | 0 | `'p'` | `{p:0}` | 否 | 0 | 1 |
|
||
| 2 | 1 | `'w'` | `{p:0, w:1}` | 否 | 0 | 2 |
|
||
| 3 | 2 | `'w'` | `{p:0, w:2}` | **是**（lastPos['w']=1 ≥ left=0 → left=2） | 2 | 2 |
|
||
| 4 | 3 | `'k'` | `{p:0, w:2, k:3}` | 否 | 2 | 2 |
|
||
| 5 | 4 | `'e'` | `{p:0, w:2, k:3, e:4}` | 否 | 2 | 3 |
|
||
| 6 | 5 | `'w'` | `{p:0, w:5, k:3, e:4}` | **是**（lastPos['w']=2 ≥ left=2 → left=3） | 3 | 3 |
|
||
|
||
最终结果：**maxLen = 3**，对应子串 `"wke"`。
|
||
|
||
**时间复杂度：O(n)** — 左右指针各遍历整个字符串一次，总共 2n 步，均摊 O(n)。
|
||
**空间复杂度：O(m)** — m 为字符集大小（ASCII 256，固定常数，实际 O(1)）。
|
||
|
||
---
|
||
|
||
## 代码提示
|
||
|
||
```
|
||
// 伪代码模板
|
||
初始化哈希表 lastPos
|
||
left = 0
|
||
maxLen = 0
|
||
|
||
for right 从 0 到 len(s)-1:
|
||
char = s[right]
|
||
|
||
if char 在 lastPos 中 且 lastPos[char] >= left:
|
||
left = lastPos[char] + 1
|
||
|
||
maxLen = max(maxLen, right - left + 1)
|
||
lastPos[char] = right
|
||
|
||
return maxLen
|
||
```
|
||
|
||
Go 语言中利用 `range` 返回的 `rune` 类型天然匹配 `map[rune]int`：
|
||
|
||
```go
|
||
// Go 风格精简版骨架
|
||
lastPos := make(map[rune]int) // 字符 -> 最后出现位置的映射
|
||
left, maxLen := 0, 0
|
||
|
||
for right, char := range s {
|
||
if pos, ok := lastPos[char]; ok && pos >= left {
|
||
left = pos + 1
|
||
}
|
||
if length := right - left + 1; length > maxLen {
|
||
maxLen = length
|
||
}
|
||
lastPos[char] = right
|
||
}
|
||
|
||
return maxLen
|
||
```
|
||
|
||
> [!note] 🐹 Go 中 string range 的返回值语义
|
||
> `for i, c := range s` 返回的 `c` 是 `rune`（4 字节 UTF-8 码点），而不是 `byte`。因此 map 应声明为 `map[rune]int`，这样天然支持中文等多字节 Unicode 字符，无需任何类型转换。
|
||
|
||
---
|
||
|
||
## 技巧
|
||
|
||
> [!tip] 🔑 核心模式：最大化窗口（Maximizing Window）
|
||
>
|
||
> 本题是滑动窗口的一类经典范式——**找满足某个条件的最大/最小窗口**。通用结构：
|
||
> 1. 右指针不断扩张
|
||
> 2. 检查条件是否被破坏
|
||
> 3. 如果破坏了，移动左指针修复
|
||
> 4. 每一步记录最优答案
|
||
>
|
||
> 变体应用："长度最小的子数组"（LeetCode 209）、"找到字符串中所有字母异位词"（LeetCode 438）。
|
||
|
||
> [!note] 🐹 Go 中 string range 的返回语义
|
||
> `for i, c := range s` 返回的 `c` 是 `rune`（即 `int32`），表示 UTF-8 码点。因此应使用 `map[rune]int` 而非 `map[byte]int`，这样天然支持中文等多字节 Unicode 字符，无需任何类型转换。
|
||
|
||
> [!info] 📊 两种滑动窗口对比
|
||
> | 模式 | 收缩条件 | 典型问题 | 本题采用 |
|
||
> |------|----------|----------|----------|
|
||
> | 最小窗口（遇违规再缩） | 窗口非法时收缩 | 最小覆盖子串 | ❌ |
|
||
> | 最大化窗口（扩展中记录） | 扩展过程中记录 | 无重复字符最长子串 ✅ | ✅ |
|
||
|
||
> [!danger] ⚠️ 常见陷阱
|
||
>
|
||
> **① 忘记"在窗口内"的判断**：直接用 `char 在 lastPos 中` 就收缩是错误的，会错过已经不在窗口的历史字符，导致左指针过度跳跃。正确写法是加上 `lastPos[char] >= left` 的条件。
|
||
>
|
||
> **② 空字符串边界**：`s = ""` 时应返回 0，循环自然处理（right 从 0 开始就不进循环），但仍建议在编码时留意。
|
||
>
|
||
> **③ 混淆子串与子序列**：子串必须连续（如 `"abc"`），子序列可以不连续（如 `"ace"` from `"abcde"`）。题目强调答案是**子串**长度，不要误做成子序列 DP。
|
||
|
||
---
|
||
|
||
## 代码
|
||
|
||
```go
|
||
func lengthOfLongestSubstring(s string) int {
|
||
lastPos := make(map[rune]int) // 字符 -> 最后出现位置的映射
|
||
left, maxLen := 0, 0
|
||
|
||
for right, char := range s {
|
||
// 如果字符已出现过，且在上一个窗口内部，移动左指针
|
||
if pos, ok := lastPos[char]; ok && pos >= left {
|
||
left = pos + 1
|
||
}
|
||
|
||
// 更新最长子串长度
|
||
if length := right - left + 1; length > maxLen {
|
||
maxLen = length
|
||
}
|
||
|
||
// 记录字符的最新位置
|
||
lastPos[char] = right
|
||
}
|
||
|
||
return maxLen
|
||
}
|
||
```
|
||
|
||
> [!success] ✅ 运行验证
|
||
> - **LeetCode 第 3 题**，通过率约 38%，中等难度中非常经典的滑动窗口入门题。
|
||
> - 核心洞察在于：**左指针不需要每次只走一格**——利用哈希表记录字符上次出现的位置，可以直接跳转到安全位置，避免不必要的比较。这就是滑动窗口从 O(n²) 优化到 O(n) 的关键。
|
||
> - 如果题目进一步问"最长不重复子串本身是什么"而非仅长度，只需额外记录 `bestLeft` 和 `bestRight`，返回 `s[bestLeft:bestRight+1]` 即可。这道题也常作为后续问题的基石，比如"重复 K 个字符的最长子串"。
|