双指针与滑动窗口

02 / 学习目标与先修自测

学完本课你能做什么，以及开始前需要会什么

每次移动指针，都要说得出被排除的组合为什么不会更优；再据此确定收缩条件与答案更新的位置。

先修自测：下面 5 题请先自己写答案，再展开对照。答不出的按括号里的位置补看再回来。本课假定你已完成「复合排序与并列规则」与上一课。

03 / 概念与术语

形态、不变量、扩张、收缩、增量维护

n = 10⁵ 时候选子数组约 n(n+1)/2 ≈ 5×10⁹ 个，逐个求和走不通；两个指针各自最多走 n 步。省下的前提是每次移动都说得出丢掉了什么。

04 / 对向夹逼：P3003

排序后按和的符号决定移动哪个指针

P3003「两数之和绝对值最小」：一行空格分隔的整数（最多 1000 个），找两个不同位置的数使和的绝对值最小，按从小到大输出这两个数，再输出绝对值；题面保证答案唯一。

l=0,r=4: -8+6=-2  |·|=2  记录 (-8,6,2)   和为负→l=1
l=1,r=4: -3+6= 3  |·|=3  不更优          和为正→r=3
l=1,r=3: -3+4= 1  |·|=1  更新 (-3,4,1)   和为正→r=2
l=1,r=2: -3+1=-2  |·|=2  不更优          和为负→l=2
l=2,r=2  相遇停止 → 输出 -3 4 1

记录必须在移动之前：移动后指针可能相遇，最后一对就没机会被记录；只有两个数时移动后 l = r，循环直接结束，记录被跳过（第 10 节错误表）。和恰为 0 时可以直接停止，因为绝对值不可能更小。

05 / 定长窗口：P3250

首窗求和，之后每步加新减旧

P3250「连续 k 个箱子的最大和」：第一行逗号分隔的整数（最多 10⁵ 个，每个在 [−10000, 10000]），第二行 k（小于箱子个数）；输出连续 k 个数之和的最大值。

首窗 [2,1,5] = 8
滑动: 8 - 2 + 1 = 7 → 7 - 1 + 3 = 9 → 9 - 5 + 2 = 6
max = 9（窗口 [5,1,3]）

两个约定决定对错：① 答案初值是首窗和，不是 0——全负数输入（如 -5,-3,-9、k=2）正确答案是 −8，初值 0 会输出 0；② 滑动从下标 k 开始，从 0 开始会用 nums[right - k] 访问负下标，Python 不报错而是从末尾取值，结果悄悄错掉（第 10 节错误表给出具体输出）。题面示例 2「8 / 1」只有一个数、k = 1：首窗就是答案 8。

06 / 变长窗口

变长窗口：按目标决定收缩与记录时机

每轮先把 a[r] 纳入统计量。求最长合法窗口时，违反约束就循环移出 a[l]，恢复合法后更新答案；求最短达标窗口时，只要仍然达标，就先记录答案再移出 a[l]。收缩写成 while 而不是 if——一次纳入可能要连收多格。

import sys

def main():
    data = sys.stdin.read().split()
    # 步骤 1：在这里读入数组与窗口参数
    ...
    left = 0
    state = 0            # 窗口内统计量（和 / 计数表）
    best = None
    for right in range(n):
        # 步骤 2：把 a[right] 纳入 state
        ...
        while False:     # 步骤 3：把 False 改成「约束被违反」的判断条件
            # 步骤 4：把 a[left] 移出 state，left += 1
            ...
        # 步骤 5：用当前合法窗口更新 best
        ...

main()

下面用「和 ≥ target 的最短非空子数组长度」（要求 target > 0 且元素全为非负）演示另一种问法：r 纳入后，只要窗口仍然达标就先记长度、再从左端收一格；无解返回 0。注意它与上面的练习模板是两种写法：模板在约束被违反时才收缩、收缩之后再更新答案；本例在满足约束时先记录答案、再继续收缩。

# 变长窗口的完整参考实现：和 >= target 的最短非空子数组长度；要求 target > 0、元素全为非负，无解返回 0
def min_sub_len(target, nums):
    if target <= 0:               # 非正 target 不在本例范围内：直接报错,不返回容易被误读成「无解」的 0
        raise ValueError("target 必须为正")
    total = 0
    best = 0                      # 0 表示还没找到
    l = 0
    for r, x in enumerate(nums):
        total += x                # r 进一格
        while total >= target:    # 合法就记答案、继续收
            length = r - l + 1
            if best == 0 or length < best:
                best = length
            total -= nums[l]      # l 收一格
            l += 1
    return best


assert min_sub_len(7, [2, 3, 1, 2, 4, 3]) == 2      # [4,3]
assert min_sub_len(11, [1, 1, 1, 1, 1, 1]) == 0     # 整段加起来也不够：无解记 0
assert min_sub_len(4, [4]) == 1                     # 单个元素恰好达标
assert min_sub_len(3, [1, 1, 1]) == 3               # 整段才够
assert min_sub_len(1, []) == 0                      # 空数组
assert min_sub_len(5, [0, 0, 5]) == 1               # 含 0 元素:0 不影响收缩,答案是 [5]

# 非正 target 必须报错,不能悄悄返回 0
for bad in (0, -1):
    try:
        min_sub_len(bad, [1, 2])
    except ValueError:
        pass
    else:
        raise AssertionError("target 非正时应报错")

07 / 不适用的情况

存在负数时窗口法失效

「和 ≥ target 就收缩」的正确性来自：元素全为非负，窗口一变短和一定不增，收缩不会错过答案。混进负数后删掉左端的负数反而让和变大，「左端只前进」失去保证。

r=0: 窗 [1]        和 1  < 5
r=1: 窗 [1,-1]     和 0  < 5
r=2: 窗 [1,-1,5]   和 5  ≥ 5 → 记长度 3；移出 1 → 和 4 < 5 停
窗口法答案 3；正确答案是 [5]，长度 1 —— 漏掉了

选型判断：全为非负、伸缩对合法性单调、问「最短/最长合法窗口」→ 滑动窗口；问「和恰好为 k 的子数组个数」→ 上一课的前缀和 + 哈希，它对负数同样成立。要注意这两条解决的不是同一个问题：前缀和 + 哈希数的是「和恰好等于 k」的子数组个数，不是「和 ≥ k 的最短长度」；含负数时求后者需要单调队列维护前缀最小值一类的方法，本课程不展开。上一课的进阶题 P4203 正好站在两者的分界线上。

08 / 窗口接上哈希与二维前缀和

P2805 记最近位置，P3282 用二维前缀和

两道进阶题各换一个「统计量」：P2805 的窗口约束在编号差上，用字典记每个数字最近一次出现的编号；P3282 数 c×c 正方形，用上一课补充里的二维前缀和把每个正方形的和降到 O(1)。

P2805「储物箱配对」：第一行逗号分隔的数字（最多 10⁵ 个），第二行 k；找两个数字相同、编号差 ≤ k 的箱子，输出最先找到的那对里左边的编号，没有输出 −1。遍历时每遇到一个数字，先看它最近一次出现的编号与当前编号之差是否 ≤ k，是就输出那个较早的编号；否则把最近位置更新为当前编号——不更新就会漏掉后面更近的一对。

P3282「探索地块建立」：第一行 n m c k，之后 n 行每行 m 个整数；数有多少个 c×c 正方形的和 ≥ k。二维前缀和数组（pre）里 pre[i][j] = 左上 i 行 j 列的矩形和；左上角 (i, j) 的 c×c 正方形和 = pre[i+c][j+c] − pre[i][j+c] − pre[i+c][j] + pre[i][j]（大 − 上 − 左 + 左上，加回被减两次的角）。c 大于 n 或 m 时一个都放不下，输出 0。

09 / 从步骤到程序

四道题的完整参考程序，每一步落在哪几行

先自己写完并提交一次，再展开对照。

import sys

nums = sorted(int(x) for x in sys.stdin.read().split())   # 先排序，原下标不再需要
l, r = 0, len(nums) - 1
best = None                                # (较小数, 较大数, |和|)
while l < r:
    s = nums[l] + nums[r]
    if best is None or abs(s) < best[2]:   # 先记录，再决定移动哪个指针
        best = (nums[l], nums[r], abs(s))
    if s > 0:
        r -= 1                             # 和为正：换更小的右端
    elif s < 0:
        l += 1                             # 和为负：换更大的左端
    else:
        break                              # 和为 0 已是最小
print(best[0], best[1], best[2])

import sys

lines = sys.stdin.read().split("\n")
nums = [int(x) for x in lines[0].strip().split(",")]   # 第一行逗号分隔
k = int(lines[1].strip())                              # 第二行窗口长度

win = sum(nums[:k])                        # 首窗：下标 0..k-1
best = win                                 # 答案初值必须是首窗和，不能是 0（全负数时 0 是错的）
for right in range(k, len(nums)):          # 从下标 k 起，每步加新减旧
    win += nums[right]
    win -= nums[right - k]
    if win > best:
        best = win
print(best)

import sys

lines = sys.stdin.read().split("\n")
nums = [int(x) for x in lines[0].strip().split(",")]
k = int(lines[1].strip())

last = {}                                  # 数字 → 它最近一次出现的编号
ans = -1
for i, num in enumerate(nums):
    if num in last and i - last[num] <= k: # 与最近一次出现的编号差不超过 k
        ans = last[num]                    # 输出这对里左边的编号
        break
    last[num] = i                          # 无论有没有出现过，都更新为最近位置
print(ans)

import sys

data = sys.stdin.read().split()
n, m, c, k = int(data[0]), int(data[1]), int(data[2]), int(data[3])
vals = [int(x) for x in data[4:4 + n * m]]
grid = [vals[i * m:(i + 1) * m] for i in range(n)]

if c > n or c > m:                         # 放不下任何一个 c×c 正方形
    print(0)
else:
    pre = [[0] * (m + 1) for _ in range(n + 1)]   # pre[i][j] = 左上 i 行 j 列的矩形和
    for i in range(n):
        for j in range(m):
            pre[i + 1][j + 1] = pre[i][j + 1] + pre[i + 1][j] - pre[i][j] + grid[i][j]
    ans = 0
    for i in range(n - c + 1):             # 左上角 (i, j)
        for j in range(m - c + 1):
            s = pre[i + c][j + c] - pre[i][j + c] - pre[i + c][j] + pre[i][j]   # 大 − 上 − 左 + 左上
            if s >= k:
                ans += 1
    print(ans)

10 / 边界、反例与复杂度

错误做法在具体输入上各输出什么

下面每一行都是一个具体的错误程序，给出输入、错误输出与正确输出；把参考程序改成对应写法就能复现。

11 / 渐进练习与参考答案

跟做 → 改一个条件 → 独立实现 → 迁移

每题先在纸上或文件里做完，再展开答案。

练习 1（跟做）：按第 05 节表的格式，对 P3250 输入 3,-1,4,-1,5,-9,2 / 3 逐步写出每个窗口的和与最大值。

练习 2（改一个条件）：把第 06 节的 min_sub_len 改成求「和 ≤ target 的最长子数组长度」（元素非负）。收缩条件和答案更新时机各怎么改？对 target = 7、a = [2, 3, 1, 2, 4, 3] 手算。

练习 3（改一个条件）：P3003 改成「若有多对答案，输出较小数更小的那一对」，第 04 节的严格小于要改吗？用 -5 -2 1 4 说明。

练习 4（独立实现）：完成「必做任务 1」的 max_fixed_window 与 closest_abs_pair，再各加一条断言：全负数 [−5, −3, −9]、k=2 应得 −8；只有两个数 [2, 3] 应得 (2, 3, 5)。

def max_fixed_window(a, k):
    win = sum(a[:k])                  # 首窗：下标 0..k-1
    best = win                        # 初值是首窗和，不是 0
    for right in range(k, len(a)):    # 从下标 k 起，每步加新减旧
        win += a[right] - a[right - k]
        best = max(best, win)
    return best

assert max_fixed_window([2, 1, 5, 1, 3, 2], 3) == 9   # 窗口 [5,1,3]
assert max_fixed_window([1, 2], 2) == 3
assert max_fixed_window([-5, -3, -9], 2) == -8         # 全负数：初值为 0 会错

def closest_abs_pair(nums):
    a = sorted(nums)
    l, r = 0, len(a) - 1
    best = None
    while l < r:
        s = a[l] + a[r]
        if best is None or abs(s) < best[2]:   # 先记录再移动
            best = (a[l], a[r], abs(s))
        if s > 0:
            r -= 1
        elif s < 0:
            l += 1
        else:
            break
    return best

assert closest_abs_pair([1, 4, -3, 6, -8]) == (-3, 4, 1)
assert closest_abs_pair([-1, -3, 7, 5, 11, 15]) == (-3, 5, 2)   # P3003 题面示例
assert closest_abs_pair([2, 3]) == (2, 3, 5)                    # 只有一对

练习 5（迁移）：P3282 输入 3 3 2 10 / 1 2 3 / 4 5 6 / 7 8 9，先写出 4×4 的前缀和数组（pre），再用「大 − 上 − 左 + 左上」算出四个 2×2 正方形的和与答案。

12 / 读题要求与复习自评

四道题的要求对照，以及完成本课之后怎么复习

提交前把下表过一遍；题目页的题面与样例是最终依据。

题解入口：需要对照解法时，先展开本课第 09 节的四份完整参考程序；四道题的题目页另有思路与参考代码，可在题目页查看。复习与自评：本课算完成 = 两道必做题 P3003、P3250 都通过判题，并勾选全部六条「学习完成检查」（含复习题 AI023 那一条）；进阶练习不影响完成状态。六条检查是自评，不改变题目的通过（AC）状态。复习时用三个问题自测：① 不看正文，说出 P3003 和为正时为什么移动右指针、丢掉了哪些组合；② 不看表格，重算 2,10,-3,-8,40,5、k=4 的三个窗口和；③ 举出一个含负数时「和 ≥ target 就收缩」失效的输入。答不出哪一条，就回到对应的节重读，再做第 11 节对应的练习。

基础加练（选做）

同一主题的 5 道基础题

这组题目采用标准输入输出（ACM 模式）：程序从标准输入读取数据、把结果写到标准输出。它们难度低于必做题，适合在必做题之前热身，或在未通过时回来巩固；不计入本课完成标准。每道题给出练习重点、完成标准与提示；已在本站通过的题目会直接显示为已通过。

• ·H100014未开始

  移动零

  基础练习 1：同向双指针 · 预计 15 分钟

  练习重点：

  写指针只接收非零值，保持相对顺序

  完成标准：

  能说出写指针左边是什么、剩余位置何时补零

  提示

  先把非零值依次写到前面，再把剩下的位置补零；输出一行，元素之间用单个空格分隔，行末不留多余空格。

  打开题目看动画讲解
• ·H100003未开始

  盛最多水的容器

  基础练习 2：对向双指针 · 预计 20 分钟

  练习重点：

  每步计算面积后移动短的那条边

  完成标准：

  能解释为什么移动长板不可能得到更大面积

  提示

  面积 = 宽度 × 两条边中较小的高度。两条边等高时移动任意一侧都可以：宽度减一，较小的高度不会增大，因此不会漏掉更大的面积。

  打开题目看动画讲解
• ·H100029未开始

  长度最小的子数组

  重点练习 · 预计 30 分钟

  练习重点：

  外层右端点扩张、内层 while 循环收缩的滑动窗口模板

  完成标准：

  能不看资料写出模板，并说出内层退出时窗口满足什么

  提示

  本题元素全为正，窗口收缩才是安全的（含负数时这个模板不成立）。答案在收缩前更新：窗口和一旦大于等于目标值（target）就记录 r - l + 1，再把左端点右移到窗口和小于 target 为止。没有满足条件的窗口时输出 0。

  打开题目看动画讲解
• ·H100002未开始

  无重复字符的最长子串

  进阶练习：窗口 + 哈希 · 预计 20 分钟

  练习重点：

  用最后出现位置表让左端 l 一步跳到位

  完成标准：

  能说清字符串 abba 里 l 为什么不能回退

  提示

  记最后出现下标表 last[ch]；遇到重复且 last[ch] >= l 时，l 跳到 last[ch] + 1。l 只能前进，回退会把重复字符重新包含进窗口。

  打开题目看动画讲解
• ·H100004未开始

  三数之和

  进阶练习：排序 + 对向 · 预计 25 分钟

  练习重点：

  固定 i 后在右侧做对向双指针，三层去重

  完成标准：

  能指出三处去重各自防住什么重复

  提示

  先排序。i 跳过与前一个相同的值；命中后 l、r 同时前进并跳过重复；输出前按字典序整理，第一行是数量 m。

  打开题目看动画讲解