leetcode-go/滑动窗口/08-无重复字符的最长子串.md

---
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 个字符的最长子串"。