3. 无重复字符的最长子串（中等）

Blind 75 › 3. 无重复字符的最长子串（中等） （第 2 章）
文章工具

题目

给定一个字符串 s，请找出其中不含重复字符的最长连续子串，返回它的长度。

所谓「子串」必须是原串里连续的一段；只要这一段里出现过两次相同字符，它就是不合法的。

自造示例：s = "xyzzxk" → 最长无重复子串是 "xyz"（也可是 "zxk"），长度为 3。

边界示例：s = "" → 0；s = "aaaa" → 1。

约束：0 ≤ s.length ≤ 105；字符可为英文字母、数字、符号与空格。

思路

一句话：用「滑动窗口」维护一个始终无重复字符的区间，右端负责扩张，左端只在出现重复时收缩。

最直白的做法：枚举所有子串。左端点有 n 种、右端点也有 n 种，一共 O(n²) 个候选子串；每个子串再逐个判重 O(n)，总时间 O(n³)。n 到 105 时完全无法接受。

稍好一点：固定每个左端点，向右逐个扩大窗口，遇到重复立刻停下并记录长度。判重被摊进了扩展过程，但最坏仍是 O(n²)，同样不够。

关键观察在于窗口条件的单调性：右端点右移只会让窗口「更可能重复」，左端点右移只会让窗口「更可能合法」。于是维护区间 [left, right] 无重复时，读到新字符 s[right]：

  • 若它不在窗口里，直接收纳并尝试更新答案；
  • 若它已存在，唯一要做的是把 left 不断右移，把旧的重复字符挤出去。left 不必回退，right 也无需回退。

这样两个指针都只会向右走，总移动 O(n)；再用哈希集合做到 O(1) 判断「当前字符是否在窗口内」。

解法

用哈希集合 seen 保存窗口内已有的字符，用 left、right 表示窗口两端：

  1. 遍历 right = 0 .. n-1。
  2. 若 s[right] 已在 seen 中，则重复：循环删除 s[left] 并让 left++，直到 s[right] 不再出现。
  3. 把 s[right] 加入集合，此时 [left, right] 无重复。
  4. 用 right - left + 1 更新最长长度。

以 s = "xyzzxk" 为例：

right读入操作窗口答案
0x不重复，直接入窗“x”1
1y不重复，直接入窗“xy”2
2z不重复，直接入窗“xyz”3
3z重复，依次弹出 x、y、z，再补入新 z“z”3
4x不重复，直接入窗“zx”3
5k不重复，直接入窗“zxk”3

注意第 right = 3 步：旧 z 在窗口内部，必须把左端的 x、y 以及旧的 z 一起弹掉，这正是为什么要用 while 收缩。

下图把上面 4 个步骤串成流程，并逐步演示：

3. 无重复字符的最长子串（中等） 解法步骤流程图
图① 解法步骤流程图（共 4 步）。
3. 无重复字符的最长子串（中等） 按步骤逐步执行的动画
动图② 按步骤依次推进（循环播放）。

C++

C++ 片段需补全 main() 函数才能运行在实训台打开 →
class Solution {
public:
 int lengthOfLongestSubstring(string s) {
 unordered_set<char>
🔒
本篇为付费内容
您已阅读试读部分，购买后即可解锁全文。
⚠️ 本站内容已做唯一性标记并受版权保护，未经授权禁止转载，侵权必究。