核心要点

  • 模板：右指针 right 不断扩张纳入新元素，破坏约束时左指针 left 收缩，直到窗口重新合法

  • 求最长：在窗口合法时更新答案；求最短：在窗口满足条件时更新答案再收缩

  • 复杂度：左右指针各最多移动 n 次，时间 O(n)，用哈希表/计数器维护窗口状态

标准回答

滑动窗口本质是用左右两个指针维护一个动态区间，适合求满足某约束的连续子串/子数组的最长或最短长度。通用模板是：右指针每次纳入一个新元素，若此时违反约束（如出现重复、和超过目标），就移动左指针收缩窗口直到重新合法。区别在于更新答案的时机——求最长时在窗口合法的状态下记录长度，求最短时在窗口刚好满足条件时记录并继续收缩。下面以「无重复字符的最长子串」为例：

python
def length_of_longest_substring(s: str) -> int:
    # 求最长无重复字符子串：右扩纳入，遇重复则左缩
    last_seen = {}     # 字符 -> 最近一次出现的下标
    left = 0
    best = 0
    for right, ch in enumerate(s):
        # 若字符在窗口内出现过，左指针跳到重复位置的右侧
        if ch in last_seen and last_seen[ch] >= left:
            left = last_seen[ch] + 1
        last_seen[ch] = right
        # 当前窗口 [left, right] 内无重复，更新最长长度
        best = max(best, right - left + 1)
    return best


if __name__ == '__main__':
    print(length_of_longest_substring('abcabcbb'))  # 3 ('abc')
    print(length_of_longest_substring('bbbbb'))      # 1 ('b')
    print(length_of_longest_substring('pwwkew'))     # 3 ('wke')

常见误区

⚠️ 常见踩坑

更新 left 时要判断 last_seen[ch] >= left，否则窗口外的旧重复会把 left 错误地往回拉；只有 left 单调不减才能保证 O(n)。

追问

追问 1：滑动窗口的时间复杂度为什么是 O(n) 而不是 O(n²)？

虽然有内外两层逻辑，但 left 和 right 都只单调向右移动，各自最多走 n 步，总移动次数 O(n)。哈希表查询为均摊 O(1)，故整体 O(n)、空间 O(字符集大小)。

追问 2：如果改成求「最短」满足条件的子串（如和 ≥ target），模板怎么变？

右指针扩张直到窗口满足条件，然后进入 while 循环不断收缩左指针并在每次满足时更新最短长度，收缩到不再满足为止。核心是「最长在合法时更新、最短在满足时收缩并更新」。

延伸学习

与本题相关的知识库文章、术语、工具与行业资讯。

🎯 相关面试题