03_滑动窗口

滑动窗口

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. 对撞指针（双指针从两端向中间）

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

# 找到两个索引 i 和 j，使得 a_i + a_j = x
# 前提：数组已排序
n = int(input())
x = int(input())
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")

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

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

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

# 求时间总和不超过 t 的最多任务数
n = int(input())
t = int(input())
timeNeed = [int(input()) for _ in range(n)]

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"）

滑动窗口通用模板

# 通用框架
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)

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

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

# 区间不同种类数查询（离线 + 双指针）
# 输入: 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)

最大子数组和（Kadane 算法）

适用场景：求连续子数组的最大和

算法思想：动态规划，cur 表示以当前位置结尾的最大子数组和

• 若 cur >= 0：继续累加（对后续有贡献）
• 若 cur < 0：重置为 0（负数只会让和更小，不如重新开始）

n = int(input())
a = [int(x) for x in input().split()]

cur = 0  # 以当前位置结尾的最大子数组和
ans = float('-inf')  # 全局最大和
for i in range(n):
    cur += a[i]
    ans = max(ans, cur)
    if cur < 0:
        cur = 0  # 负数没有贡献，重新开始
print(ans)