---
title: LeetCode 第3题：无重复字符的最长子串问题深度解析，从暴力到滑动窗口哈希表优化的逐步指南
created: 2026-03-16
updated: 2026-03-16
type: summary
tags: ["algorithm", "hash", "notes", "sliding", "telegram"]
external: http://go/ui/posts/2182/
---

同学你好，看到你在研究 LeetCode 的第 3 题“无重复字符的最长子串”，这是一道非常经典且重要的算法题。别担心，让我们一步步来把它弄懂吃透。

### 🧐 第一步：彻底理解题目在问什么

首先，我们得确保完全理解了题目的意思。题目要求我们在一个字符串中，找到一个**连续的子串**，这个子串里所有的字符都**不能重复**，然后返回这个子串的最大长度。

这里有几个关键点，从你提供的链接里的讨论也能看出，很多同学一开始会混淆：
1.  **子串 (Substring) 必须是连续的**。比如在 `"pwwkew"` 中，`"pwke"` 虽然字符不重复，但它跳过了中间的 `'w'`，不是连续的，所以不算子串，正确答案是连续的 `"wke"` 或 `"kew"`，长度是 3。
2.  **重复是指整个子串内字符不能重复**。不是指不能有连续相同的字符，比如 `"dvdf"`，答案是长度为 3 的 `"vdf"`，而不是你第一眼可能想到的 `"dv"` 或 `"df"`。

### 💡 第二步：从最直观的想法开始——暴力解法

作为一个中学生，我们遇到新问题，可以先从最直接、最符合直觉的方法开始想，然后再慢慢优化。

*   **思路**：我们可以检查这个字符串的**所有**可能的连续子串，对每一个子串，判断它里面的字符是否都唯一，然后记录下满足条件的最长长度。
*   **如何操作**：假设字符串长度为 n，我们需要用两个循环来枚举所有子串的起点 `i` 和终点 `j`，然后再用一个循环或者集合来判断子串 `s[i:j+1]` 是否有重复字符。
*   **复杂度分析**：这种方法的时间复杂度大约是 **O(n³)**。当字符串长度 n 很大时（题目中 n 最大可达 5*10⁴），计算机需要执行天文数字般的操作，是绝对行不通的。正如 LeetCode 讨论区里有人提醒的：**“不要试图用暴力解法通过此题。”**

所以，我们需要一个更聪明的方法。

### 🚀 第三步：巧妙的优化——滑动窗口算法

**滑动窗口**是解决这类子串、子数组问题的神器。你可以把它想象成一条可以在字符串上移动的“毛毛虫”。

*   **核心思想**：我们维护一个**窗口**（也就是一个子串），并保证这个窗口内的所有字符都是**不重复**的。然后我们让窗口的右侧不断地向前探索，加入新字符。如果新字符加入后导致了重复，我们就从窗口的左侧开始收缩，直到把这个重复的字符移出窗口为止。在整个过程中，我们时刻记录窗口的最大长度。

让我们用例子 `s = "abcabcbb"` 来走一遍：

| 步骤 | 当前窗口 (存储的字符) | 右侧指针 (探索新字符) | 遇到的情况与操作 | 当前窗口长度 | 最大长度 |
| :--- | :--- | :--- | :--- | :--- | :--- |
| 1 | [ ] | 指向索引 0，字符 'a' | 窗口为空，直接加入 'a'。 | 1 | 1 |
| 2 | [a] | 指向索引 1，字符 'b' | 'b' 不在窗口中，加入 'b'。 | 2 | 2 |
| 3 | [a, b] | 指向索引 2，字符 'c' | 'c' 不在窗口中，加入 'c'。 | 3 | 3 |
| 4 | [a, b, c] | 指向索引 3，字符 'a' | **'a' 已经在窗口中！** 我们需要移动左侧指针，直到把原来的 'a' 移出去。 | - | 3 |
| 5 | 窗口移除最左侧的 'a'，变为 [b, c] | 右侧指针仍指向索引 3，字符 'a' | 现在窗口中只有 `b` 和 `c`，不包含 'a'，所以可以加入 'a'，窗口变为 [b, c, a]。 | 3 | 3 |
| 6 | [b, c, a] | 指向索引 4，字符 'b' | **'b' 在窗口中！** 移动左侧指针，移除 'b'。 | - | 3 |
| 7 | 窗口移除 'b'，变为 [c, a] | 右侧指针仍指向索引 4，字符 'b' | 窗口 [c, a] 不包含 'b'，加入 'b'，窗口变为 [c, a, b]。 | 3 | 3 |
| 8 | [c, a, b] | 指向索引 5，字符 'c' | **'c' 在窗口中！** 移动左侧指针，移除 'c'。 | - | 3 |
| 9 | 窗口移除 'c'，变为 [a, b] | 右侧指针仍指向索引 5，字符 'c' | 窗口 [a, b] 不包含 'c'，加入 'c'，窗口变为 [a, b, c]。 | 3 | 3 |
| 10 | [a, b, c] | 指向索引 6，字符 'b' | **'b' 在窗口中！** 移动左侧指针，依次移除 'a'、'b'，直到把 'b' 移出。 | - | 3 |
| 11 | 窗口移除了 'a'、'b'，变为 [c] | 右侧指针仍指向索引 6，字符 'b' | 窗口 [c] 不包含 'b'，加入 'b'，窗口变为 [c, b]。 | 2 | 3 |
| 12 | [c, b] | 指向索引 7，字符 'b' | **'b' 在窗口中！** 移动左侧指针，移除 'c'、'b'。 | - | 3 |
| 13 | 窗口清空 [ ] | 右侧指针仍指向索引 7，字符 'b' | 窗口为空，加入 'b'，窗口变为 [b]。 | 1 | 3 |
| **结束** | | | 字符串遍历完毕，整个过程记录到的最大长度为 **3**。 | | |

### 💻 第四步：如何用代码实现

要实现这个算法，我们需要一个“助手”来帮我们快速知道一个字符是否已经在当前窗口里，以及它在什么位置。这个助手可以是一个**哈希集合 (HashSet)** 或者**哈希表 (HashMap)**。

*   **方法一：使用哈希集合 (HashSet)**
    我们用一个集合 `charSet` 来存储窗口内的字符。用两个指针 `left` 和 `right` 表示窗口的左右边界。
    1.  当 `right` 指针指向的字符不在 `charSet` 中时，就把它加入集合，并更新最大长度，然后 `right` 右移。
    2.  如果字符已在集合中，就从集合中移除 `left` 指针指向的字符，并把 `left` 右移。重复这个过程，直到窗口中没有重复字符。

*   **方法二：使用哈希表 (HashMap) 优化**
    使用哈希集合，我们需要一个 `while` 循环来逐步移动左指针。而使用哈希表，我们可以直接**存储每个字符最后出现的位置**。当遇到重复字符时，我们可以直接把 `left` 指针跳到**上一个重复字符位置的下一个位置**，效率更高。

    这是用哈希表的 Python 代码示例，你可以参考一下逻辑：
    ```python
    class Solution:
        def lengthOfLongestSubstring(self, s: str) -> int:
            char_index_map = {}  # 哈希表，存储字符和它最后出现的索引
            max_length = 0
            left = 0  # 窗口左边界

            for right in range(len(s)):
                current_char = s[right]
                # 如果当前字符在哈希表中，且它的位置在左边界右边（或等于），说明在当前窗口内重复了
                if current_char in char_index_map and char_index_map[current_char] >= left:
                    # 直接把左边界跳到上一个重复字符的下一个位置
                    left = char_index_map[current_char] + 1
                
                # 更新字符的最新位置
                char_index_map[current_char] = right
                # 计算当前窗口长度，并更新最大长度
                current_length = right - left + 1
                if current_length > max_length:
                    max_length = current_length

            return max_length
    ```

### 📊 第五步：复杂度分析与总结

*   **时间复杂度**：**O(n)**。其中 n 是字符串的长度。我们只需要用 `right` 指针遍历一次字符串，`left` 指针也只会向前移动，所以每个字符最多被访问两次。
*   **空间复杂度**：**O(min(m, n))**。m 是字符集的大小（比如字母、数字、符号的总数），n 是字符串长度。哈希表或哈希集合的大小取决于窗口的大小，但最多不会超过字符集的大小或字符串长度。

对于你这样的中学生来说，理解并掌握**滑动窗口**思想，并学会用**哈希表**来优化，是攻克这类题目的关键。这道题就是一个非常典型的例子，务必亲手在 LeetCode 上运行通过，并尝试用不同的测试用例（比如 `" "`、`"dvdf"`、`"tmmzuxt"`）来验证你的代码。

如果在理解代码或者运行过程中遇到任何问题，随时可以再来问我。祝你刷题顺利，享受AC（Accepted）的快乐！
