滑动窗口算法是一种用于处理数组或链表等线性数据结构的优化技术，尤其适用于解决子数组/子串问题（如求最大/最小和、最长/最短子串等）。其核心思想是通过动态调整窗口的左右边界，避免重复计算，将时间复杂度从暴力解法的 (O(n^2)) 优化至 (O(n))。

核心概念

1. 窗口：由左右指针（left 和 right）定义的子数组/子串范围。
2. 动态调整：
   • 右指针扩展：向右移动 right，扩大窗口以包含新元素。
   • 左指针收缩：当窗口不满足条件时，向右移动 left，缩小窗口。
3. 目标：在遍历过程中维护窗口的某种性质（如和、唯一字符数等），并记录最优解。

算法步骤

1. 初始化：left = 0，result 记录最优解（如最大值、最小值等）。
2. 遍历数组：移动右指针 right 从 0 到 n-1。
3. 维护窗口性质：
   • 根据问题要求更新窗口内的状态（如当前和、字符频率等）。
   • 如果窗口不满足条件（如和超过目标值、出现重复字符等），移动 left 缩小窗口。
4. 更新结果：每次满足条件时，比较并更新 result。
5. 返回结果：遍历结束后返回 result。

经典问题示例

1. 无重复字符的最长子串

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

解法：

• 使用哈希表记录字符最后出现的位置。
• 移动 right，若当前字符已存在且在窗口内，则移动 left 到重复字符的下一个位置。
• 更新最大长度。

def lengthOfLongestSubstring(s: str) -> int:
    char_index = {}
    left = max_len = 0
    for right, char in enumerate(s):
        if char in char_index and char_index[char] >= left:
            left = char_index[char] + 1
        char_index[char] = right
        max_len = max(max_len, right - left + 1)
    return max_len

2. 最小覆盖子串

问题：给定字符串 s 和 t，找到 s 中包含 t 所有字符的最短子串。

解法：

• 使用哈希表统计 t 的字符频率（need）。
• 移动 right 扩展窗口，满足条件后移动 left 缩小窗口。
• 记录满足条件的最小窗口。

from collections import defaultdict

def minWindow(s: str, t: str) -> str:
    need = defaultdict(int)
    for char in t:
        need[char] += 1
    left = min_len = 0
    count = 0  # 记录已匹配的字符数
    result = ""
    
    for right, char in enumerate(s):
        if char in need:
            if need[char] > 0:
                count += 1
            need[char] -= 1
        
        while count == len(t):
            if right - left + 1 < min_len or min_len == 0:
                min_len = right - left + 1
                result = s[left:right+1]
            left_char = s[left]
            if left_char in need:
                need[left_char] += 1
                if need[left_char] > 0:
                    count -= 1
            left += 1
    return result

3. 滑动窗口最大值

问题：给定数组 nums 和窗口大小 k，返回每个窗口的最大值。

解法（单调队列优化）：

• 使用双端队列维护窗口内的单调递减序列。
• 队首元素即为当前窗口最大值。

from collections import deque

def maxSlidingWindow(nums: list[int], k: int) -> list[int]:
    q = deque()
    result = []
    for i in range(len(nums)):
        while q and nums[i] > nums[q[-1]]:
            q.pop()
        q.append(i)
        if q[0] == i - k:
            q.popleft()
        if i >= k - 1:
            result.append(nums[q[0]])
    return result

关键点总结

• 窗口性质：明确窗口需要满足的条件（如无重复、包含特定字符等）。
• 指针移动：right 始终向前，left 根据条件动态调整。
• 哈希表/数组：用于快速统计窗口内元素的状态（如频率、存在性）。
• 时间复杂度：通常为 (O(n))，每个元素最多被 left 和 right 访问一次。

滑动窗口算法通过巧妙地维护窗口状态，避免了暴力解法的重复计算，是解决子数组/子串问题的高效工具。