Hot100 3 | 无重复字符的最长子串：从暴力到滑动窗口

系列导航：LeetCode Hot100 刷题导航（系列导航） · 上一篇：Hot100 42 | 接雨水：按列思考到双指针收缩 · 下一篇：Hot100 438 | 找到字符串中所有字母异位词：定长滑动窗口

从这一题开始，系列正式进入 滑动窗口 专题。和前面的双指针题相比，这类题不再主要关心“左右两端怎么夹逼出最优值”，而是更关心：

当前窗口里装了什么
窗口什么时候合法
不合法时应该怎么缩

如果你能把这题真正看懂，后面的很多字符串窗口题都会顺很多。

专栏导读

这题看起来不难，但它非常适合用来建立“窗口思维”。

因为你会第一次明确体会到：

右指针负责把新字符放进窗口
左指针负责把窗口修回合法状态
整个算法不是在枚举所有子串，而是在维护一个始终尽量大的“合法窗口”

这篇会重点讲清楚下面几件事：

题目要找的到底是什么
为什么暴力法虽然正确但很笨
滑动窗口里的 left、right、seen 分别代表什么
为什么发现重复后，要用 while 一直缩，而不是只缩一步

1. 题目到底在说什么

题目给你一个字符串 s，要你找出：

其中最长的一个子串
这个子串里不能有重复字符

最后返回的不是这个子串本身，而是它的长度。

例如：

1	s = "abcabcbb"

最长的不重复子串是：

"abc"

长度是：

2. 这里的“子串”是什么意思

这题第一眼最容易混的地方，就是：

子串
子序列

这两个词不是一回事。

2.1 子串

子串要求：

必须连续

例如字符串：

abcabcbb

其中：

abc
bca
cab

这些都是子串，因为它们都来自原字符串里连续的一段。

2.2 子序列

子序列则不要求连续，只要顺序不乱就行。

比如：

acb

就不是这里要找的对象。

所以这题你从一开始就必须记住：

我们找的是连续的一段字符

3. 题目真正想让你找什么

这题表面上是在问：

最长长度是多少？

但本质上它在问的是：

当你不断向右扩展一段字符串时
怎么快速判断这段里有没有重复字符
一旦有重复，怎么把它修回合法状态

这就是滑动窗口的味道。

4. 先用例子把题意看明白

还是：

1	s = "abcabcbb"

你如果从左往右看，会发现：

a 没重复，长度 1
ab 没重复，长度 2
abc 没重复，长度 3
再加一个 a，就重复了

这时候你就不能继续把窗口无脑扩大，而是必须把左边一些字符移出去，直到窗口重新不重复。

这其实已经很接近滑动窗口的核心了。

5. 方法一：暴力枚举

5.1 最直观的想法

如果第一次做这题，最自然的思路是：

枚举每一个起点 i
从这个起点一路往后看
只要还没重复，就继续延伸
一旦重复，就停下来
记录从这个起点能得到的最长长度

这就是最朴素的暴力法。

5.2 Python Tutor 版代码

def length_of_longest_substring(s):
    ans = 0

    for i in range(len(s)):
        seen = set()

        for j in range(i, len(s)):
            if s[j] in seen:
                break

            seen.add(s[j])
            ans = max(ans, j - i + 1)

    return ans

print(length_of_longest_substring("abcabcbb"))

5.3 LeetCode 可提交版代码

class Solution:
    def lengthOfLongestSubstring(self, s):
        ans = 0

        for i in range(len(s)):
            seen = set()

            for j in range(i, len(s)):
                if s[j] in seen:
                    break

                seen.add(s[j])
                ans = max(ans, j - i + 1)

        return ans

5.4 每一行代码在做什么

先看：

ans = 0

表示当前找到的最大长度，初始为 0。

再看外层循环：

1	for i in range(len(s)):

这里的 i 表示：

当前尝试的子串起点

也就是说，程序会尝试：

从下标 0 开始的子串
从下标 1 开始的子串
从下标 2 开始的子串
…

然后：

1	seen = set()

这里的 seen 表示：

从当前起点 i 出发，已经遇到过哪些字符

为什么每次外层循环都要新建一个空集合？

因为：

每换一个新的起点
我们就在重新检查一段新的子串
之前记录过的字符不能直接沿用

接着看内层循环：

1	for j in range(i, len(s)):

这里的 j 表示：

当前正在尝试把子串延伸到哪个位置

于是当前候选子串其实就是：

s[i:j+1]

再看判断：

1 2	if s[j] in seen: break

它的意思是：

如果当前这个新字符以前已经见过了
那就说明当前子串出现了重复字符
于是从当前起点出发，再往后延伸已经没有意义了
直接停掉这一轮

如果没有重复：

1 2	seen.add(s[j]) ans = max(ans, j - i + 1)

第一句是把当前字符加入集合；
第二句是更新当前找到的最大长度。

这里的长度为什么是：

j - i + 1

因为：

起点是 i
终点是 j
两端都算进去，所以要加 1

5.5 用示例手动走一遍

还是：

1	s = "abcabcbb"

从 `i = 0` 开始

开始时：

seen = {}

往后扫：

j = 0，字符是 a，没重复，加入集合
j = 1，字符是 b，没重复，加入集合
j = 2，字符是 c，没重复，加入集合
j = 3，字符又是 a，重复了，停下

所以从下标 0 开始，最长长度是 3。

从 `i = 1` 开始

重新开一轮：

seen = {}

这时能得到：

bca

长度还是 3。

后面继续尝试不同起点，最终全局最大值仍然是 3。

5.6 这个方法的问题在哪

问题不是它错，而是它太重复了。

因为：

从 i = 0 开始时，你已经检查了 abc
从 i = 1 开始时，你又检查了 bca
很多工作其实重复做了很多次

这就是为什么我们要进一步优化。

6. 方法二：滑动窗口（真正推荐）

6.1 先把“窗口”想象成人话

你可以把窗口理解成字符串上的一个可伸缩区间：

1	[left, right]

这个区间表示：

当前这段子串，是我们正在维护的候选答案

这题里我们希望这个窗口始终满足：

里面没有重复字符

只要这个条件成立，它就是“合法窗口”。

6.2 核心想法

滑动窗口的整体逻辑是：

让 right 不断向右扩张窗口
每加入一个新字符，就检查窗口是否合法
如果不合法，说明出现重复字符
这时移动 left，把窗口缩小，直到重新合法
在每次窗口合法时，用它的长度更新答案

你可以把它记成一句话：

右边负责加字符，左边负责修重复

7. 滑动窗口 Python Tutor 版代码

def length_of_longest_substring(s):
    seen = set()
    left = 0
    ans = 0

    for right in range(len(s)):
        while s[right] in seen:
            seen.remove(s[left])
            left += 1

        seen.add(s[right])
        ans = max(ans, right - left + 1)

    return ans

print(length_of_longest_substring("abcabcbb"))

8. LeetCode 可提交版代码

class Solution:
    def lengthOfLongestSubstring(self, s):
        seen = set()
        left = 0
        ans = 0

        for right in range(len(s)):
            while s[right] in seen:
                seen.remove(s[left])
                left += 1

            seen.add(s[right])
            ans = max(ans, right - left + 1)

        return ans

9. 每一行代码在做什么

先看初始化：

1
2
3

seen = set()
left = 0
ans = 0

这里每个变量都有自己的明确职责：

seen：记录当前窗口里有哪些字符
left：窗口左边界
ans：目前找到的最大合法窗口长度

然后看循环：

1	for right in range(len(s)):

这里的 right 表示：

窗口右边界
它会从左到右，把每个字符依次尝试放进窗口里

所以可以把它理解成：

right 在不断试图“扩张窗口”

最关键的是这段：

1
2
3

while s[right] in seen:
    seen.remove(s[left])
    left += 1

这三行是整道题的核心。

它的含义是：

如果当前准备加入的字符 s[right] 已经在窗口里
那窗口就不合法了，因为出现了重复
这时不能继续扩张，而要不断移动 left
把左边字符一个个移出去
直到这个重复问题被消掉

这里为什么一定要用 while，而不是 if？

因为有时候只移走一个字符还不够。

例如：

abba

当你处理最后一个 a 时，窗口里可能不只是有一个字符需要排出去。必须持续缩，直到窗口重新不重复，所以必须写 while。

再看：

1	seen.add(s[right])

这句表示：

现在窗口已经合法了
可以正式把 s[right] 放进窗口

最后更新答案：

1	ans = max(ans, right - left + 1)

为什么这一步一定要放在窗口合法之后？

因为只有合法窗口才有资格参与比较。

如果你在窗口还重复的时候就更新答案，就会把错误长度算进去。

10. 用经典示例一步一步模拟

示例：

1	s = "abcabcbb"

第 1 轮：`right = 0`

当前字符是 a。

a 不在 seen 里
所以直接加入

这时：

窗口是 "a"
left = 0
right = 0
ans = 1

第 2 轮：`right = 1`

当前字符是 b。

b 不重复
直接加入

这时：

窗口是 "ab"
长度是 2
ans = 2

第 3 轮：`right = 2`

当前字符是 c。

c 也不重复

这时：

窗口是 "abc"
长度是 3
ans = 3

第 4 轮：`right = 3`

当前字符又是 a。

这时：

a 已经在窗口 "abc" 里了
所以窗口不合法

于是开始移动 left：

移走 s[left] = 'a'
left 从 0 变成 1

现在重复问题解决了，因为窗口里已经没有旧的 a。

然后再把新的 a 加进去。

这时窗口变成：

"bca"

长度还是 3。

后面继续走

后面你会继续得到一些不重复窗口，比如：

"cab"
"abc"

但都不会超过长度 3。

所以最终答案还是：

11. 为什么这方法比暴力法更聪明

暴力法的问题在于：

每换一个起点，就重新从头检查一遍

滑动窗口聪明的地方在于：

它不会把整段窗口完全推倒重来
而是尽量复用已经检查过的部分

也就是说：

右边持续向前走
左边只在必要时才跟着走

这样整体效率就高很多。

12. 这题还可以再优化吗

可以。

更进阶的写法会用一个字典记录“字符上一次出现的位置”，这样可以更快跳过一段区间，而不是一个个 remove。

不过如果你现在还在滑动窗口入门阶段，我更建议你先真正吃透这一版集合写法，因为：

它结构清晰
好理解
很适合你建立窗口思维

等你把这一版完全看懂，再去学“记录最后出现位置”的版本会顺很多。

13. 这题顺手学到的 Python 语法

13.1 `set()`

创建一个集合，用来快速判断某个字符是否出现过。

13.2 `in`

1	if s[right] in seen:

表示判断当前字符是否已经在集合中。

13.3 `remove()`

1	seen.remove(s[left])

表示把左边字符从当前窗口的集合记录中删掉。

13.4 `while`

这题里 while 不是装饰，它表示：

只要窗口还不合法
就继续缩

14. 这题最容易犯的错

14.1 把子串和子序列混掉

这题只认连续的一段。

14.2 发现重复后只缩一步

这往往不够，所以这里必须用 while，而不是 if。

14.3 在窗口还不合法时就更新答案

答案只能在窗口已经不重复之后更新。

14.4 没看懂 `left` 的意义

left 不是单纯“左边那个下标”，它真正代表的是：

当前合法窗口的左边界

15. 一句话复盘

这题的本质不是枚举所有子串，而是维护一个始终没有重复字符的窗口；右边负责扩张，左边负责消重，窗口合法时再更新答案。

16. 下一步怎么学

下一题 438. 找到字符串中所有字母异位词 会继续练滑动窗口，不过会从“窗口内容不能重复”切换成“窗口长度固定、字符计数要匹配”。