用窗口在序列上滑动，O(n)时间解决子串子数组问题
滑动窗口（Sliding Window）是双指针的特殊形式，维护一个"窗口"在序列上滑动。窗口的左右边界可以分别扩展和收缩，从而在 O(n) 时间内解决许多看似需要 O(n²) 或 O(n³) 的子串/子数组问题。核心思想是：右指针扩展窗口探索新元素，左指针收缩窗口满足约束条件。
# 可变大小窗口模板
def sliding_window(s):
from collections import defaultdict
window = defaultdict(int)
left = 0
result = 0 # 根据题意初始化
for right, ch in enumerate(s):
# 1. 右指针扩展：加入新元素
window[ch] += 1
# 2. 判断窗口是否需要收缩
while 窗口不满足条件:
# 左指针收缩：移除左侧元素
window[s[left]] -= 1
left += 1
# 3. 更新答案
result = max(result, right - left + 1)
return result| 题目类型 | 窗口维护的内容 | 数据结构 |
|---|---|---|
| 无重复字符的最长子串 | 字符出现次数 | 哈希字典 / 数组 |
| 最小覆盖子串 | 目标字符的满足数量 | 哈希字典 + 计数器 |
| 长度最小的子数组 | 子数组和 | 变量累加 |
| 滑动窗口最大值 | 窗口内最大值 | 单调队列 |
题目描述：给定一个字符串 s，请你找出其中不含有重复字符的最长子串的长度。
left = max(left, last_pos + 1)。class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
last_pos = {} # 字符 → 最近出现的位置
left = 0
max_len = 0
for right, ch in enumerate(s):
if ch in last_pos:
left = max(left, last_pos[ch] + 1)
last_pos[ch] = right
max_len = max(max_len, right - left + 1)
return max_len时间复杂度：O(n) — 每个字符最多被访问两次
空间复杂度：O(min(m, n)) — m 为字符集大小
题目描述：给你一个字符串 s 和一个字符串 t。返回 s 中涵盖 t 所有字符（包括重复字符）的最小子串。如果不存在，返回空字符串。
class Solution:
def minWindow(self, s: str, t: str) -> str:
from collections import defaultdict
need = defaultdict(int)
for ch in t:
need[ch] += 1
window = defaultdict(int)
valid = 0
left = 0
start, min_len = 0, float('inf')
for right, ch in enumerate(s):
if ch in need:
window[ch] += 1
if window[ch] == need[ch]:
valid += 1
while valid == len(need):
if right - left + 1 < min_len:
start = left
min_len = right - left + 1
left_ch = s[left]
if left_ch in need:
if window[left_ch] == need[left_ch]:
valid -= 1
window[left_ch] -= 1
left += 1
return s[start:start + min_len] if min_len != float('inf') else ""时间复杂度：O(n) — 每个字符最多进出窗口各一次
空间复杂度：O(k) — k 为 t 中不同字符数
题目描述：给定一个含有 n 个正整数的数组和一个正整数 target，找出该数组中满足其和 ≥ target 的长度最小的连续子数组，并返回其长度。如果不存在，返回 0。
class Solution:
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
left = 0
window_sum = 0
min_len = float('inf')
for right in range(len(nums)):
window_sum += nums[right]
while window_sum >= target:
min_len = min(min_len, right - left + 1)
window_sum -= nums[left]
left += 1
return min_len if min_len != float('inf') else 0时间复杂度：O(n) — 每个元素最多进出窗口各一次
空间复杂度：O(1) — 只用几个变量