04_滑动窗口

滑动窗口

滑动窗口通用模板

# 通用框架
l = 0
ans = 0  # 或其他初始化
for r in range(n):
    # 1. 将 arr[r] 加入窗口（扩展右边界）
    # ...

    # 2. 窗口不满足条件时，收缩左边界
    while 不满足条件:
        # 移除 arr[l]
        # ...
        l += 1

    # 3. 更新答案
    ans = max(ans, r - l + 1)

概念

双指针方法通过在数组中迭代两个指针来跟踪满足某些条件的索引。有两种常见的变体：

1. 两个指针从数组的两端开始，并相互移动。

2. 两个指针以不同速度沿同一方向移动。这种变体被称为滑动窗口算法。

1. 固定窗口大小（求最大/最小窗口和）

适用场景：给定固定大小 k，求所有窗口中最大/最小的和

def sliding_window(arr, k):
    """求大小为 k 的窗口的最大和"""
    window_sum = sum(arr[:k])  # 初始化第一个窗口的和
    max_sum = window_sum
    for i in range(k, len(arr)):
        # 滑动窗口：加入新元素 arr[i]，移除旧元素 arr[i-k]
        window_sum += arr[i] - arr[i-k]
        max_sum = max(max_sum, window_sum)
    return max_sum

2. 对撞指针（双指针从两端向中间）

适用场景：有序数组中找两个数之和等于目标值

https://cses.fi/problemset/task/1640

我们要找到两个索引 $i$ 和 $j$ ，使得 $a_i + a_j = x$。

我们可以先对数组进行排序。然后，将左指针初始化在数组的开头（ $l=0$ ），将右指针初始化在末尾（ $r=N−1$ ）。

当 $lx$ ，和太大。为了减少和，我们减少 $r$

由于数组已排序，将左指针向右移动永远不会减少和，将右指针向左移动永远不会增加和。

# 找到两个索引 i 和 j，使得 a_i + a_j = x
# 前提：数组已排序
n, x = map(int, input().split())

nums = [(int(input()), i) for i in range(n)]  # (值, 原索引)
nums.sort()  # 按值排序

l = 0
r = n - 1
while l < r:
    s = nums[l][0] + nums[r][0]
    if s == x:
        print(nums[l][1] + 1, nums[r][1] + 1)  # 输出原索引（1-indexed）
        exit()
    elif s < x:
        l += 1  # 和太小，左指针右移
    else:
        r -= 1  # 和太大，右指针左移
print("IMPOSSIBLE")

Time Complexity: $\mathcal{O}(N \log N)$ 时间复杂度： $\mathcal{O}(N \log N)$

同一道题的另一种解法：无序数组用哈希表一遍扫描，见 1. 两数之和。注意对撞指针要求数组有序（对应 LC 167 两数之和 II）；无序数组要么先排序（$O(n \log n)$，还需记录原下标），要么直接用哈希（$O(n)$）。

3. 可变窗口（双指针同向）

场景一：满足条件的最长/最短窗口

滑动窗口方法是双指针技术的一种变体，其中两个指针沿同一方向移动以维护一个特定的元素范围或”窗口”。虽然标准双指针通常相互靠近移动，但滑动窗口技术用于找到一个满足条件的连续子数组。

适用场景：窗口和 ≤ t 的最大长度

https://codeforces.com/contest/279/problem/B

我们想要找到可以在 $t$ 分钟内读完的最长的连续书籍段，即寻找最长的连续子数组，要求子数组的和小于 $t$

为了实现这一点，我们可以定义 $\texttt{left}$ 和 $\texttt{right}$ 来表示段的开始和结束。两者都将从数组的开头开始。这些数字可以被视为指针，因此得名”双指针”。

由于两个指针最多移动 $N$ 次，整体时间复杂度为 $\mathcal{O}(N)$ 。

# 求时间总和不超过 t 的最多任务数
n, t = map(int, input().split())
timeNeed = list(map(int, input().split()))

l = 0
sum_time = 0
ans = 0
for r in range(n):
    sum_time += timeNeed[r]  # 右指针扩展窗口
    while sum_time > t and l <= r:  # 窗口不满足条件，左指针收缩
        sum_time -= timeNeed[l]
        l += 1
    ans = max(ans, r - l + 1)  # 更新最大窗口长度
print(ans)

场景二：无重复元素的最长窗口

适用场景：求不含重复元素的最长子串/子数组

# 求无重复字符的最长子串长度
s = input().strip()
n = len(s)
arr = list(s)

window = set()
l = 0
ans = 0
for r in range(n):
    while arr[r] in window:  # 当前字符已存在，收缩窗口
        window.remove(arr[l])
        l += 1
    window.add(arr[r])
    ans = max(ans, r - l + 1)
print(ans)

# 示例：
# 输入："abcabcbb"
# 输出：3（"abc"）

场景三：离线区间查询（莫队思想）

适用场景：多个区间查询，按端点排序后用双指针处理

# 区间不同种类数查询（离线 + 双指针）
# 输入: n=种类数, w=区间跨度, K=查询数, M=记录数
# 记录格式: (时间, 种类ID)
# 查询: 给定起始时间 S，求 [S, S+w-1] 区间内的不同种类数

# 1. 构建查询 (起始, 结束, 索引)
queries = [(S[i], S[i] + w - 1, i) for i in range(K)]
queries.sort(key=lambda x: x[1])  # 按结束时间排序（离线处理关键）

# 2. 记录按时间排序
records.sort()

# 3. 双指针滑动窗口
ans = [0] * K
l = r = 0
cnt = 0
appear = {}  # 种类ID -> 出现次数

for start, end, idx in queries:
    # 右指针：扩展到 end
    while r < len(records) and records[r][0] <= end:
        id = records[r][1]
        appear[id] = appear.get(id, 0) + 1
        if appear[id] == 1:
            cnt += 1
        r += 1

    # 左指针：收缩到 start
    while l < len(records) and records[l][0] < start:
        id = records[l][1]
        appear[id] -= 1
        if appear[id] == 0:
            cnt -= 1
        l += 1

    ans[idx] = cnt

# 离线处理优势：利用区间端点的单调性，避免重复计算
# 时间复杂度：O(M log K + M) = O(M log K)