滑动窗口算法介绍（Sliding Window）解决连续区间问题

滑动窗口算法简介

滑动窗口（Sliding Window）是一种基于双指针的算法思想，通过维护一个动态的窗口（连续区间），优化数组或字符串问题的求解效率。其核心是通过单层循环替代暴力枚举的嵌套循环，将时间复杂度从 $O(n^2)$ 降低到 $O(n)$。

核心思想

1. 窗口定义：使用两个指针 left 和 right 定义一个窗口，窗口内的元素满足特定条件。

2. 动态调整：

- 扩展窗口：右指针 right 向右移动，将新元素加入窗口。

- 收缩窗口：当窗口不满足条件时，左指针 left 向右移动，缩小窗口范围。

3. 优化目标：通过单向移动指针，避免重复计算，快速找到满足条件的最优解（如最长/最短子串、最大值等）。

适用场景

1. 连续子数组/子串问题：如最长无重复子串、最小覆盖子串。

2. 固定窗口大小问题：如求固定长度的子数组最大和。

3. 多条件匹配问题：如统计包含特定字符的子串数量。

算法流程图（Mermaid）

代码模板

def sliding_window(s):
    left = 0
    result = 0
    window = set()  # 用于维护窗口状态
    for right in range(len(s)):
        # 扩展窗口
        while s[right] in window:
            window.remove(s[left])
            left += 1
        window.add(s[right])
        result = max(result, right - left + 1)
    return result

经典示例：最长无重复子串

问题：给定字符串 s，找出不含有重复字符的最长子串的长度。

滑动窗口解法：

1. 使用哈希表或集合记录窗口内字符。

2. 右指针 right 遍历字符串，若字符未重复，加入窗口。

3. 若字符重复，左指针 left 移动直到窗口内无重复。

4. 更新最大长度。

代码实现：

def lengthOfLongestSubstring(s: str) -> int:
    char_set = set()
    left = 0
    max_len = 0
    for right in range(len(s)):
        while s[right] in char_set:
            char_set.remove(s[left])
            left += 1
        char_set.add(s[right])
        max_len = max(max_len, right - left + 1)
    return max_len

性能对比

总结

滑动窗口算法通过单向移动指针和维护窗口状态，高效解决连续区间问题。其优势在于：

1. 减少重复计算：避免暴力枚举所有子串。

2. 线性时间复杂度：指针 left 和 right 各遍历一次数据。

3. 灵活适应场景：适用于固定窗口、动态窗口、多条件匹配等多种问题。