数据结构与算法 / 系统课时

用滑动窗口维护连续区间

用滑动窗口维护连续区间

很多连续子数组或子串问题并不需要枚举所有区间。滑动窗口用左右边界维护一个“当前候选区间”,右端负责纳入新元素,左端在约束被破坏时收缩。本篇用“最长无重复子串”拆解扩张、收缩和窗口状态三件事。

学习目标

  • 识别适合滑动窗口的连续区间问题
  • 掌握“右边界扩张、左边界收缩、窗口状态同步”的循环顺序
  • 用哈希集合维护无重复窗口,并正确更新最优答案

窗口为什么能压缩搜索

暴力枚举长度为 nn 的所有连续区间需要检查 O(n2)O(n^2) 个候选。滑动窗口利用题目的单调性:当右端加入新元素后窗口变得非法,只要不断右移左端就能重新合法;已经被左端丢弃的起点无需回头尝试。

“最长无重复子串”满足这一条件。右端加入字符后,若出现重复,收缩左端一定不会让重复更多,因此可以持续缩小直到窗口重新合法。

滑动窗口扩张与收缩流程

固定扩张与收缩顺序

循环时让 right 逐个读取字符。若当前字符已在窗口集合中,先持续移动 left 并删除离开的字符;直到重复消失,再把当前字符加入集合,最后用窗口长度更新答案。

python
def length_of_longest_substring(s):
    window = set()
    left = 0
    best = 0

    for right, ch in enumerate(s):
        # 当前字符重复时,左边界持续收缩直到窗口重新合法
        while ch in window:
            window.remove(s[left])
            left += 1

        window.add(ch)
        best = max(best, right - left + 1)

    return best

print(length_of_longest_substring('abcabcbb'))

预期输出

text
3

答案对应任意一个长度为 3 的无重复窗口,例如 abc。这里必须使用 while 而不是 if:一次右移左边界未必足以消除重复,窗口需要持续收缩到约束恢复为止。

窗口状态必须与边界同步

滑动窗口常见错误不是边界公式,而是“边界动了,状态没动”。如果左端字符离开窗口,却忘记从集合、计数器或频次表中删除,状态就不再代表 [left, right],后续判断会全部失真。

可以把每轮循环理解为三个阶段:先让右端尝试进入;若约束被破坏就移动左端并同步清理状态;窗口重新合法后再统计答案。这个顺序比背诵具体题目的代码更重要。

判断题目是否适合滑窗

滑动窗口通常同时满足两个条件:目标是连续区间,并且非法窗口能通过单向移动左边界恢复合法。无重复、和不超过阈值、至多包含若干种字符等问题常见于这一模式。

如果收缩左边界后状态并不呈单调改善,例如包含任意正负数时要求子数组和恰好等于某值,普通滑窗往往失效。先验证“右扩张会怎样、左收缩能否稳定修复约束”,再决定是否套用窗口框架,能避免把双指针机械用在不适合的问题上。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

用滑动窗口维护连续区间

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通