跳转到内容

无重复字符的最长子串,滑动窗口怎样避免重复扫描?

用左右边界维护一个不含重复字符的连续窗口。右边界遇到字符 c 时,若 c 上一次出现的位置仍在窗口里,把左边界移动到那个位置之后;否则左边界不动。记录每个字符最近位置,并更新最大窗口长度。

无重复字符的最长子串,滑动窗口怎样避免重复扫描?图解。窗口内没有重复字符;遇重复,只把左边界右移;left 不能退回去;子串必须连续。

关键更新是 left = max(left, last[c] + 1),不能让左边界往回退。例如 abba 处理最后一个 a 时,它旧的位置已在窗口外,不能据此扩大成仍有重复字符的窗口。

在哈希操作期望常数时间的前提下,每个位置处理一次,时间 O(n),额外空间由不同字符数决定。子串必须连续,不能误答成去掉重复字符后的子序列。还要先明确按字节、Unicode 码点还是用户感知字符计数。

资料

核对于 2026-10-16。LeetCode longest substring。工程场景与实现取舍由本站解释,不代表原帖公司的实际架构。