---
title: 深入解析力扣经典题目：最长无重复字符子串的滑动窗口解法与Python实现
created: 2026-03-16
updated: 2026-03-16
type: summary
tags: ["algorithm", "notes", "string", "telegram", "window"]
external: http://go/ui/posts/2184/
status: inbox
---

当然可以！让我们像探险家研究地图一样，一起深入解析这道经典题目。我会尽量用你能理解的方式解释清楚。

---

## **首先，我们来仔细看懂这道题**

**题目要求**：给定一个字符串（比如 `"abcabcbb"`），找出其中**没有重复字符**的最长**连续子串**，返回它的长度。

**例子1**：
- 输入：`"abcabcbb"`
- 输出：`3`
- 解释：最长无重复子串是 `"abc"`，长度为3。注意 `"bca"`、`"cab"` 也都是长度为3的无重复子串，但我们只要长度。

**例子2**：
- 输入：`"bbbbb"`
- 输出：`1`
- 解释：全是重复的 `'b'`，所以最长只能是 `"b"`，长度为1。

**例子3**：
- 输入：`"pwwkew"`
- 输出：`3`
- 解释：最长无重复子串是 `"wke"`（注意：`"pwke"` 不是子串，因为子串必须是连续的）。

**关键概念提醒**：
1. **子串**：必须是原字符串中**连续**的一段。
2. **无重复字符**：这段连续的字符中，每个字符只能出现一次。

---

## **最直观的方法（但效率不高）**

想象你有一个放大镜，每次检查一段连续的字符，看看里面有没有重复。

**怎么做**：
1. 遍历字符串的每一个字符作为起点。
2. 从这个起点开始，一个一个往后看，把看到的字符记在一个小本本上（比如一个集合）。
3. 如果看到的新字符已经在小本本里了，就停止，记录当前长度。
4. 比较所有起点找到的长度，取最大的。

**例子**：`"abcabcbb"`
- 从 `'a'` 开始：看到 `'a'`(记下)→ `'b'`(记下)→ `'c'`(记下)→ `'a'`(重复了！停)。长度3。
- 从 `'b'` 开始：`'b'`→ `'c'`→ `'a'`→ `'b'`(重复)。长度3。
- ……继续从 `'c'`、`'a'` 等开始。

**问题**：如果字符串很长（比如1万个字符），这种方法会做很多重复工作，速度会很慢。时间复杂度大约是 O(n²)（n是字符串长度），在LeetCode上会超时。

---

## **更聪明的方法：滑动窗口**

这是解决这类“连续子串/子数组”问题的常用技巧。名字听起来高级，但思想很像我们用**两个手指夹住一段字符串**。

**想象一下**：
1. 你有**左手指**（L）和**右手指**（R），它们夹住的区域就是当前检查的子串。
2. 开始时，两个手指都指在字符串开头。
3. **右手指**负责向右探索，扩大窗口。
4. **左手指**负责在发现重复时，向右收缩窗口，直到没有重复为止。

**我们需要一个“记事本”来记录窗口里有什么字符**。在编程中，我们通常用一个**哈希集合**（可以想象成一个特殊的书包，放进去的东西没有顺序，但你能立刻知道某个东西在不在里面）。

### **具体步骤（我们用例子跟着做一遍）**

例子：`"abcabcbb"`

| 步骤 | L | R | 窗口内容 | 记事本（集合） | 发生了什么 | 当前长度 | 最大长度 |
|------|---|---|----------|----------------|------------|----------|----------|
| 0    | 0 | 0 | `"a"`    | {a}            | 初始        | 1        | 1        |
| 1    | 0 | 1 | `"ab"`   | {a, b}        | R右移，加入'b' | 2        | 2        |
| 2    | 0 | 2 | `"abc"`  | {a, b, c}     | R右移，加入'c' | 3        | 3        |
| 3    | 0 | 3 | `"abca"` | {a, b, c, **a重复**} | R右移到'a'，发现重复！ | —        | —        |
| 4    | **1** | 3 | `"bca"`  | {a, b, c}     | L右移，直到去掉重复的'a'（从窗口去掉第一个'a'） | 3        | 3        |
| 5    | 1 | 4 | `"bcab"` | {a, b, c, **b重复**} | R右移到'b'，重复 | —        | —        |
| 6    | **2** | 4 | `"cab"`  | {a, b, c}     | L右移，去掉重复的'b' | 3        | 3        |
| 7    | 2 | 5 | `"cabc"` | {a, b, c, **c重复**} | R右移到'c'，重复 | —        | —        |
| 8    | **3** | 5 | `"abc"`  | {a, b, c}     | L右移，去掉重复的'c' | 3        | 3        |
| 9    | 3 | 6 | `"abcb"` | {a, b, c, **b重复**} | R右移到'b'，重复 | —        | —        |
| 10   | **4** | 6 | `"cb"`   | {b, c}        | L右移，去掉重复的'b'（这次要去掉两个'b'？不对！实际上每次只移动一位，因为要去掉窗口最左边的字符） | 2        | 3        |
| ...  |   |   |          |                | 继续直到R到末尾 |          |          |

**关键点**：
- **右指针R**：像探路者，每次向右走一步，把新字符加入窗口。
- **左指针L**：像清洁工，当发现重复时，不断向右移动，并把左边界的字符从记事本中移除，直到新加入的字符（R指的）在记事本中唯一。
- **记事本**：我们用哈希集合（Python中的`set`）来记录窗口里有哪些字符，这样检查“是否重复”只需要O(1)时间（非常快）。

**为什么这样更快**？
- 每个字符最多被左指针L和右指针R各访问一次。
- 时间复杂度：**O(n)**，n是字符串长度。即使字符串很长，也能很快算出来。

---

## **用Python代码实现（简单版）**

```python
def lengthOfLongestSubstring(s: str) -> int:
    # 记事本：当前窗口里的字符集合
    char_set = set()
    
    # 左指针，初始为0
    left = 0
    
    # 记录最大长度
    max_length = 0
    
    # 右指针从0开始，一直走到字符串末尾
    for right in range(len(s)):
        # 如果当前字符已经在记事本里（重复了）
        while s[right] in char_set:
            # 移除左指针的字符，并将左指针右移
            char_set.remove(s[left])
            left += 1
        
        # 现在s[right]不在记事本里了，加入它
        char_set.add(s[right])
        
        # 更新最大长度
        current_length = right - left + 1
        max_length = max(max_length, current_length)
    
    return max_length
```

**代码逐行解释**：
1. `char_set = set()`：准备一个空的“记事本”（集合）。
2. `left = 0`：左手指放在开头。
3. `max_length = 0`：目前找到的最大长度是0。
4. `for right in range(len(s))`：右手指`right`从0开始，一步一步向右走。
5. `while s[right] in char_set`：如果右手指指向的字符已经在记事本里（说明重复了）。
6. `char_set.remove(s[left])`：把左手指的字符从记事本擦掉。
7. `left += 1`：左手指向右挪一步。
8. 循环继续，直到记事本里没有重复的`s[right]`。
9. `char_set.add(s[right])`：现在可以安全地把右手指的字符加入记事本了。
10. `current_length = right - left + 1`：当前窗口长度。
11. `max_length = max(max_length, current_length)`：更新最大长度。
12. 最后返回`max_length`。

---

## **亲自试一试**

用这个代码跑一下例子，验证你的理解：

- `"abcabcbb"` → 输出 `3`
- `"bbbbb"` → 输出 `1`
- `"pwwkew"` → 输出 `3`
- `""`（空字符串） → 输出 `0`
- `"abcdefg"`（全部不同） → 输出 `7`

---

## **可能遇到的困惑点**

1. **为什么是`while`而不是`if`？**
   - 因为可能需要移除多个字符才能消除重复。例如窗口`"abca"`，新字符`'a'`与开头的`'a'`重复，但移除一个`'a'`后，窗口变成`"bca"`，新字符`'a'`不再重复。但如果是`"abba"`，新字符`'a'`加入时，窗口是`"abb"`，需要移除两个`'b'`才能让`'a'`不重复。

2. **窗口长度计算**：
   - `right - left + 1` 是因为`left`和`right`都是索引（从0开始），所以要加1。比如`left=0, right=2`，实际是3个字符。

3. **空间复杂度**：
   - 我们用了一个集合，最坏情况下（所有字符都不同），集合大小等于字符串长度，所以空间复杂度是O(n)。但通常字符集是有限的（比如ASCII只有128个字符），所以实际空间可以认为是O(1)。

---

## **总结一下解题思路**

1. **问题类型**：求满足条件的最长连续子串/子数组。
2. **核心技巧**：**滑动窗口** + **哈希集合**快速检查重复。
3. **关键步骤**：
   - 右指针扩张窗口，左指针收缩窗口。
   - 用集合记录窗口内容，保证窗口内无重复。
   - 每次移动后更新最大长度。

**给你的建议**：
- 先在纸上模拟滑动窗口的过程，就像我上面表格里做的那样。
- 然后尝试自己写出代码，可能第一次写会有些小错误，没关系，调试就是学习的过程。
- 理解后，你可以尝试解决一些类似的题目，比如LeetCode的第438题（找到所有字母异位词），也是用滑动窗口。

如果还有哪里不清楚，或者想让我用其他方式解释，随时告诉我！学习算法就像学习骑自行车，一开始可能会摇晃，但一旦掌握，就能自由前行。加油！
