滑动窗口的入场券：为什么元素必须是正的

/* MD / 富文本中的 .toc（含博客园搬家等嵌套结构）；.toc-box 在侧栏，不受影响 */
#content_views .toc,
/* 编辑器常在目录前后插入空 p（:empty 仍占 20px），一并去掉避免顶空隙 */
#content_views.markdown_views > p:empty:has(+ .toc),
#content_views.markdown_views > .toc + p:empty,
/* 富文本旧版目录标记 */
#content_views.htmledit_views #main-toc,
#content_views.htmledit_views #hr-toc,
#content_views.htmledit_views p[id*=\”-toc\”] {
display: none !important;
}
/* 目录去掉后，紧跟的首个标题不再多出一块上边距 */
#content_views.markdown_views > .toc + h1,
#content_views.markdown_views > .toc + h2,
#content_views.markdown_views > .toc + h3,
#content_views.markdown_views > .toc + h4,
#content_views.markdown_views > .toc + p:empty + h1,
#content_views.markdown_views > .toc + p:empty + h2,
#content_views.markdown_views > .toc + p:empty + h3,
#content_views.markdown_views > .toc + p:empty + h4 {
margin-top: 0 !important;
}

滑动窗口的入场券：为什么元素必须是正的

题目：

一排 n 个座位，第 i 个座位上坐着 a_i 个人（保证 a_i ≥ 1）。
挑一段连续的座位，要求这段人数之和 ≥ S。
在所有满足要求的选法里，输出座位数最少的那一种长度。凑不出来输出 -1。

输入 输出
10 15 2
5 1 3 5 10 7 4 9 2 8

n ≤ 10⁶。

暴力解法很清楚：枚举所有区间，求和，挑最短的。n = 10⁶ 时区间数是 n(n+1)/2 ≈ 5×10¹¹，跑不完。

正解是「滑动窗口 / 双指针」，代码不到 20 行。但大多数人学会的是代码长什么样，没学会它什么时候才成立 —— 这篇主要讲后半件事。

先看完整脚本

import sys

def main():
data = sys.stdin.buffer.read().split()
n = int(data[0]); S = int(data[1])
a = [0] + [int(x) for x in data[2:2 + n]] # 下标从 1 开始

l = 0 # 窗口左端（不含）
cur = 0 # 窗口内人数之和
ans = n + 1 # 哨兵：比任何可能答案都大

for r in range(1, n + 1):
cur += a[r] # 右端进来一个
while cur >= S: # 只要还够，就一直往左缩
ans = min(ans, r – l) # 现在这个窗口是合法的，记长度
l += 1
cur -= a[l] # 左端出去一个

print(–1 if ans == n + 1 else ans)

main()

样例跑出 2。下面把每一处都拆开。

（写法说明：这里用 l 表示「窗口左端前一个位置」，所以窗口是 (l, r]，长度是 r – l。换成「l 指向窗口内第一个元素、长度 r-l+1」也完全可以，两种都对 —— 但整份代码里必须统一一种，混着写必错。）

第一步：窗口是什么

窗口就是一个左闭右开的感觉：一个左端、一个右端、一个和。

a: 5 1 3 5 10 7 4 9
└───────┬───────┘
窗口 [1,4]，和 = 5+1+3+5 = 14

只有三个量，别的什么都不用记：l、r、cur。

这是它比暴力省事的根本原因：暴力每换一个区间就重算一次和（O(长度)），而窗口移动一格只改一个数 —— 进一个、出一个，都是 O(1)。

第二步：什么时候扩、什么时候缩

两条规则，就是整个算法的全部：

右端一直往右走（每个 r 都要被处理一次，一次不能漏）
↓ 进来一个 a[r]，cur 变大
只要 cur >= S 成立，就：
记一次答案（当前窗口是合法的）
挪左端，把 a[l] 从 cur 里减掉

为什么「只要够就一直缩」？因为题目要最短。当前窗口已经满足条件了，那就试试能不能更短 —— 往左缩一格，如果还满足，就还更短。

缩到不满足为止，再进下一个右端。

用样例走几步（S = 15）：

答案 2。

第三步：为什么不会漏掉更优解

这是双指针真正需要想清楚的地方。很多人会用，但说不清为什么对 —— 说不清就等于在碰运气。

关键一句话：

对每一个固定的右端 r，我们找到的是「以 r 结尾的所有合法区间里最短的那个」。

因为 while 一直缩到刚好不满足为止，再缩一格就不合法了。所以对每个 r，拿到的是极限，不是随便一个。

而所有可能的区间，一定是以某个 r 结尾的。既然每个 r 上的最优我们都拿到了，全局最优必然在其中。

这依赖一个前提：l 不需要回退。 也就是「当 r 变大时，最优的左端只会往右走，不会往左走」。

为什么？因为所有 a_i ≥ 1：

• r 往后挪一格，窗口里多了一个正数，和变大了
• 原来那个 l 位置上的窗口，现在仍然合法，甚至可能还能再缩一点
• 所以最优左端只会不变或变大，绝不会变小

这一条就是「单调性」，是双指针能成立的全部理由。

第四步：为什么是 O(n)

for 循环跑 n 次，r 走 n 步。

while 看起来可能很耗，但注意：l 只增不减，最多从 0 走到 n。 所以整个程序里 while 的总次数加起来不超过 n 次 —— 分摊下来每次循环 O(1)。

r 总共走 n 步 + l 总共走 n 步 = 2n

这就是「均摊 O(n)」。双指针的复杂度，永远要按「两个指针各自走了多远」算，不能按「两层循环」算。

坑一：ans = 0 当哨兵，和 min 天然打架

这是这题最容易踩、而且不报错的坑。

「还没找到答案」这件事，很多人下意识用 0 或 -1 表示：

ans = 0
...
ans = min(ans, r – l) # 完蛋

min(0, 任何正数) 永远是 0。答案会死死钉在 0 上，最后输出 0 —— 程序不崩、不报错，只是错了。

正确做法是把初值设成一个不可能被选中的大数：

ans = n + 1 # 长度最长就是 n，n+1 一定选不上
...
print(–1 if ans == n + 1 else ans)

判据也跟着变：判断的是「ans 有没有被改过」，不是「ans 是不是 0」。

通用结论：求最小值时，初值要用「无穷大」，不能用 0。 求最大值才用 0 或 -1。这条在任何语言、任何题里都成立。

顺带一句：别用 float('inf')。它能用，但 min 之后你拿到的是浮点数，print 出来是 2.0，很多判题机会判错。用整数 n+1 最安全。

坑二：两个变量都叫「段」，量纲就混了

我第一版在这里卡住：

ans = min(cur, r – l + 1) # 错

cur 是「这段里有几个人」，r-l+1 是「这段有几个座位」。拿人数和座位数比大小，逻辑上根本不成立。

错误不在语法，在命名 —— 两个东西都叫「这一段」，脑子就自动把它们当同类了。改成能看出单位的名字，这种错自己就冒出来了：

cnt_people = 0 # 几个人
len_window = r – l # 几个座位

变量名不是给自己看的，是给五分钟后的自己看的。 带单位的名字（cnt_ / len_ / sum_ / max_）能挡掉一整类错误。

坑三：缩的时候减什么

cur -= ans # 错：ans 是长度
cur -= a[l] # 对：左端那个人数

这个错通常是被上一个错带出来的：ans 算错了，cur -= ans 就跟着错。但只要记住一句话就不会错：窗口移动，一定是「某一个具体元素」进出，不可能是「一段长度」进出。

坑四：这条题最硬的一条 —— 元素必须全正

这才是这篇的正题。

a_i ≥ 1 不是「数据保证」，是「这题能用双指针」的入场券。

如果允许 0 或负数，会发生什么：

具体说：如果 a = [10, -5, 10]、S = 15：

• 窗口 [1,3] 的和是 15，长度 3
• 但 [1,1] 的和是 10，不够；[3,3] 是 10，也不够
• 而 [1,3] 缩掉 -5 之后和变成 20，比原来还大 —— 「左端缩一格，和一定变小」这条前提直接崩了

那时候 while 的退出条件就失去意义了：你以为缩到不满足就是极限，实际上再缩可能又满足了。这时候得换方法：前缀和 + 二分，或者单调队列。

所以看到「求最短/最长区间和」这类题，第一步不是写窗口，是先看元素正负。

• 全正 → 双指针，O(n)
• 有正有负 → 前缀和 + 二分 O(n log n)，或单调队列

这条判断，比记住模板有用得多。

坑五：输入可能折行

a = list(map(int, input().split())) # 只在「所有数都在一行」时对

n = 10⁶ 时很多平台确实一行给完，但有些题会折行。折行了 a 就短一截，后面要么 IndexError，要么算出个莫名其妙的答案。

兜底写法：

a = []
while len(a) < n:
a += list(map(int, input().split()))

验证：7 组边界 + 600 组对拍

边界用例，每组都对着写：

全部通过。

然后拿暴力版对拍（O(n²)，n ≤ 30，600 组随机）：

def brute(n, S, a):
best = n + 1
for i in range(n):
s = 0
for j in range(i, n):
s += a[j]
if s >= S:
best = min(best, j – i + 1)
break # 全正，再往后只会更长，直接停
return –1 if best == n + 1 else best

结果 0 / 600 不一致。

注意 brute 里那个 break：因为全正，固定起点后往后越加越长，一旦够了就没必要再试。暴力版也可以利用题目性质，只要它还能当裁判。 裁判要的是「一定对」，不是「一定慢」。

性能：跟上一题比出个反直觉的结论

n = 10⁶ 三种极端情况，同机实测（取 3 次中位数）：

都是 0.3 秒上下。

有意思的是对比：另一道同样 O(n) 的题（区间加用差分），n = m = 10⁶ 实测是 0.6 ~ 1.1 秒。

同样的复杂度，差了 2~4 倍。 差在哪？

• 差分那题要输出 10⁶ 个数字，得生成 10⁶ 个字符串再 join 成一个巨串
• 这题只输出一个数字

所以：估 Python 的时间，除了看 O()，还得看输出规模。 输入读法、输出体量、字符串拼接，这些都是「O(1) 之外的常数」，在 10⁶ 这个量级上，它们能差出好几倍。

（顺带：这两题我都试过把读入改成 sys.stdin.buffer.read().split()，实测差异不到 10%，被机器噪声完全掩盖。改读入是这类题最不值得做的优化。）

写在最后

这题的识别信号，比代码本身重要：

「连续一段」+「和最值」+「元素全正」→ 双指针。

三条缺一条就要重新想：

• 不是连续的（可以跳着选）→ 那不是区间题，是别的
• 不是最值，是「有多少种」→ 前缀和 + 哈希
• 元素有负数 → 双指针失效，上二分或单调队列

下一步我要练的：

成本：🟢 零成本零注册

纯标准库，不用装任何东西。

免责声明（请务必读完）

• 题目来自蓝桥杯练习。代码和所有输出都是本机实际跑出来的（Python 3.11，Windows）。
• 表中耗时跟机器、Python 版本、当时的后台负载都有关系，你跑出来不一样很正常 —— 看数量级，别看绝对值。
• 文中所有输入数据都是随机生成的假数据。
• 文章讲的是通用写法，不针对任何具体系统或题目。