---
title: 深入剖析LeetCode第3题“无重复字符的最长子串”：详解滑动窗口算法原理、实战与复杂度分析
created: 2026-03-16
updated: 2026-03-16
type: summary
tags: ["algorithm", "notes", "sliding", "string", "telegram"]
external: http://go/ui/posts/2183/
---

你好！很高兴能以一个“学长”的身份带你攻克这道经典的算法题。

LeetCode 第 3 题 **“无重复字符的最长子串”** 是学习算法中一个非常重要的里程碑，因为它引入了一个极具威力的方法：**滑动窗口 (Sliding Window)**。

---

## 1. 题目大意：你在找什么？

想象一下，你面前有一串长长的彩色珠子（字符串），每颗珠子上写着一个字母。你的任务是：**从中截取一段连续的珠子，要求这一段里没有任何两个珠子的颜色（字母）是重复的。** 请问，你能截取到的最长的一段是多少？

### 关键区别：子串 vs 子序列

* **子串 (Substring)**：必须是**连续**的。就像切下一段火腿肠。
* **子序列 (Subsequence)**：可以不连续。就像从火腿肠里挑出几个肉粒。

> 这道题要求的是**子串**。

---

## 2. 核心思路：滑动窗口 (Sliding Window)

如果用最笨的方法（暴力法），我们要检查每一个可能的开头和结尾，这太慢了。我们可以用更聪明的**滑动窗口**法，就像是在字符串上拉一个“伸缩拉链”。

### 动作分解：

1. **左边界 (`left`)** 和 **右边界 (`right`)**：最初都在最左边。
2. **扩张**：不断把 `right` 向右移动，把新的字符加入我们的“窗口”。
3. **冲突处理**：如果新加入的字符在窗口里**已经存在**了，说明窗口不合法了。这时候，我们要不断把 `left` 向右移动，直到把那个重复的字符“踢出去”。
4. **记录最大值**：在每一步合法的时候，记录下窗口的长度：
$$right - left + 1$$


，并更新全局最大值。

---

## 3. 手把手模拟过程

假设字符串是 `pwwkew`：

| 步骤 | 窗口内容 | 动作 | 当前长度 | 最大长度 |
| --- | --- | --- | --- | --- |
| 1 | `[p]` | `right` 移动到 p | 1 | 1 |
| 2 | `[pw]` | `right` 移动到 w | 2 | 2 |
| 3 | `[pw]w` | **冲突！** 发现第二个 w。`left` 必须右移。 | - | 2 |
| 4 | `[w]` | `left` 移过第一个 w 后，窗口变合法。 | 1 | 2 |
| 5 | `[wk]` | `right` 移动到 k | 2 | 2 |
| 6 | `[wke]` | `right` 移动到 e | 3 | **3** |
| 7 | `[wke]w` | **冲突！** 发现末尾的 w。`left` 右移。 | - | 3 |

---

## 4. 代码实现 (Python 示例)

既然你有软件工程背景，我们直接看代码实现。这里我们用一个“集合 (Set)”或者“哈希表 (Dict)”来快速判断字符是否重复。

```python
def lengthOfLongestSubstring(s: str) -> int:
    # 使用集合来存储当前窗口内的字符
    lookup = set()
    left = 0
    max_len = 0
    current_len = 0
    
    for right in range(len(s)):
        # 如果新字符已经在集合里，就从左边开始删，直到不重复
        while s[right] in lookup:
            lookup.remove(s[left])
            left += 1
            current_len -= 1
        
        # 加入新字符，更新长度
        lookup.add(s[right])
        current_len += 1
        
        # 更新历史最大长度
        if current_len > max_len:
            max_len = current_len
            
    return max_len

```

---

## 5. 算法复杂度分析

作为一名“初中生”，理解这个性能分析会让你更有竞争力：

* **时间复杂度**：$O(n)$。虽然代码里有 `while` 循环，但实际上 `left` 和 `right` 都只是从左向右走了一遍，没有回头路。每个字符最多被“进入窗口”一次和“离开窗口”一次。
* **空间复杂度**：$O(min(m, n))$。我们需要一个集合来存字符，$n$ 是字符串长度，$m$ 是字符集的大小（比如英文字母只有 26 个）。

---

### 进阶思考

如果你想追求极致性能（比如在工作中优化代码），我们可以用**哈希表记录字符最后出现的下标**。这样当发现重复时，`left` 不需要一步步挪，而是直接“瞬移”到重复字符下一个位置。

你想尝试一下这个“瞬移版”的逻辑推导吗？
