双指针朝同一个方向走，两者之间的间隔就是答案。本文讲四种滑动窗口，再加一个计数技巧：“恰好 K 个”没法直接滑动，就把它变成一次减法。
第 1 篇里，两个指针相向而行。这一篇里，它们都往右走，关键在两者之间的间隔。这个间隔就是窗口。整类题归结为两个问题：什么时候扩大窗口，什么时候收缩窗口。
下面每个程序都是完整的，都在 .NET 10 上运行过，输出直接从运行结果里复制。
为什么值得费这个劲
求任意 k 个连续值的最大和。最直接的写法是每个窗口都从头加一遍。数一数加法的次数：
// How many additions each approach needs. No timing — just the work done.
Console.WriteLine($"{"n",8} {"k",6} {"recompute",14} {"slide",10}");
foreach ((int n, int k) in new[] { (8, 3), (1_000, 100), (100_000, 1_000) })
{
long recompute = (long)(n - k + 1) * k;
long slide = k + (long)(n - k) * 2;
Console.WriteLine($"{n,8} {k,6} {recompute,14:N0} {slide,10:N0}");
}输出：
n k recompute slide
8 3 18 13
1000 100 90,100 1,900
100000 1000 99,001,000 199,0008 个元素时，18 次对 13 次，差别可以忽略。到了 10 万个元素，就是 9900 万次对 20 万次，只有后者能在时间限制内跑完。
原因是相邻窗口几乎完全重叠。每次重新计算，都把这部分重叠白白扔掉了。
模式 6 — 固定窗口
窗口宽度始终是 k。每滑一步，左边出去一个值，右边进来一个值，当前总和做一次减法、一次加法就能修正。其余 k-2 个值完全不用碰。
窗口不会重新求和。左边出去一个值（红色），右边进来一个值，当前总和只需两次运算就能修正，而不是 k 次。
int[] a = [3, 1, 4, 1, 5, 9, 2, 6];
int k = 3;
int win = 0;
for (int i = 0; i < k; i++) win += a[i];
int best = win, bestAt = 0;
Console.WriteLine($"window [0..{k - 1}] sum = {win}");
for (int r = k; r < a.Length; r++)
{
int leaving = a[r - k], entering = a[r];
win += entering - leaving;
if (win > best) { best = win; bestAt = r - k + 1; }
Console.WriteLine($"window [{r - k + 1}..{r}] -{leaving} +{entering} sum = {win}");
}
Console.WriteLine($"\nbest = {best}, starting at index {bestAt}: [{string.Join(", ", a[bestAt..(bestAt + k)])}]");输出：
window [0..2] sum = 8
window [1..3] -3 +1 sum = 6
window [2..4] -1 +5 sum = 10
window [3..5] -4 +9 sum = 15
window [4..6] -1 +2 sum = 16
window [5..7] -5 +6 sum = 17
best = 17, starting at index 5: [9, 2, 6]代价： 时间 O(n)，空间 O(1)。
适用场景： 题目替你定好了窗口大小，比如“每个长度为 k 的子串”“任意连续 k 天”。只要窗口滑动时能在 O(1) 内维护答案，就用这个模式。
模式 7 — 扩大到失效为止，记录最长
这回窗口大小没有给定，它恰恰是要求的东西。求不含重复字符的最长子串。
规则反过来了：右边一直扩大，只有窗口失效时才从左边缩小。答案是出现过的最大有效窗口。
有意思的是这里的“缩小”怎么做。遇到重复字符时，左边界不是一步一步挪，而是直接跳到上一次出现位置的后面。这一跳里藏着一个陷阱。
陷阱在最后一行。’a’ 上次出现在索引 0，但索引 0 已经不在窗口里了，所以左边界不能退回去。没有 `prev >= lo` 这个判断，lo 就会往回走，窗口失控地变大。
string s = "abba";
Dictionary<char, int> lastSeen = [];
int lo = 0, best = 0, bestAt = 0;
for (int r = 0; r < s.Length; r++)
{
char c = s[r];
if (lastSeen.TryGetValue(c, out int prev) && prev >= lo)
{
Console.WriteLine($"r={r} '{c}' seen at {prev}, and {prev} >= lo({lo}) -> lo jumps to {prev + 1}");
lo = prev + 1;
}
else if (lastSeen.TryGetValue(c, out int old))
{
Console.WriteLine($"r={r} '{c}' seen at {old}, but {old} < lo({lo}) -> it is OUTSIDE the window, lo stays");
}
else
{
Console.WriteLine($"r={r} '{c}' never seen -> lo stays {lo}");
}
lastSeen[c] = r;
int len = r - lo + 1;
if (len > best) { best = len; bestAt = lo; }
Console.WriteLine($" window [{lo}..{r}] = \"{s[lo..(r + 1)]}\" length {len}");
}
Console.WriteLine($"\nlongest = {best}, \"{s.Substring(bestAt, best)}\"");输出：
r=0 'a' never seen -> lo stays 0
window [0..0] = "a" length 1
r=1 'b' never seen -> lo stays 0
window [0..1] = "ab" length 2
r=2 'b' seen at 1, and 1 >= lo(0) -> lo jumps to 2
window [2..2] = "b" length 1
r=3 'a' seen at 0, but 0 < lo(2) -> it is OUTSIDE the window, lo stays
window [2..3] = "ba" length 2
longest = 2, "ab"看 r=3 这一行。'a' 上次出现在索引 0，但窗口从 2 开始，所以那个 'a' 已经在身后，不在窗口里了。如果把 lo 跳到 0 + 1，左边界就会往回退，窗口会悄悄重新算上早已丢掉的字符。
lo永远不能减小。凡是让左边界跳跃的窗口模式，都需要一个判断来保证这一点。
去掉 prev >= lo 这个判断，"abba" 会得到 3。这个 bug 只差几个字符，而且 "abcabc" 这类小输入测不出来。
代价： 时间 O(n)，因为每个指针只往右走。空间 O(k) 用于字典，k 是字符集大小。
适用场景： 题目要求满足某个条件的最长窗口，而且条件被破坏后，可以通过从左边移除元素来恢复。
模式 8 — 满足时就收缩，记录最短
镜像版本。求和至少为目标值的最短窗口。
扩大会让和变大，所以扩大能修复无效窗口。这意味着 while 循环换到了另一边：窗口一旦有效，就在保持有效的前提下尽量收缩，每次都记录长度。
右边扩大到窗口有效，再在保持有效的前提下从左边收缩。再缩就会失效的那一刻，就是最短答案。
int[] a = [2, 3, 1, 2, 4, 3];
int target = 7;
int lo = 0, sum = 0, best = int.MaxValue, bestAt = -1;
for (int r = 0; r < a.Length; r++)
{
sum += a[r];
Console.WriteLine($"r={r} +{a[r]} window [{lo}..{r}] sum={sum}");
while (sum >= target)
{
int len = r - lo + 1;
if (len < best) { best = len; bestAt = lo; }
Console.WriteLine($" sum {sum} >= {target}, length {len} -> shrink: drop a[{lo}]={a[lo]}");
sum -= a[lo];
lo++;
}
}
Console.WriteLine(best == int.MaxValue
? "\nno window reaches the target"
: $"\nshortest = {best}, starting at {bestAt}: [{string.Join(", ", a[bestAt..(bestAt + best)])}]");输出：
r=0 +2 window [0..0] sum=2
r=1 +3 window [0..1] sum=5
r=2 +1 window [0..2] sum=6
r=3 +2 window [0..3] sum=8
sum 8 >= 7, length 4 -> shrink: drop a[0]=2
r=4 +4 window [1..4] sum=10
sum 10 >= 7, length 4 -> shrink: drop a[1]=3
sum 7 >= 7, length 3 -> shrink: drop a[2]=1
r=5 +3 window [3..5] sum=9
sum 9 >= 7, length 3 -> shrink: drop a[3]=2
sum 7 >= 7, length 2 -> shrink: drop a[4]=4
shortest = 2, starting at 4: [4, 3]真正干活的是 while，而且必须是 while，不能是 if。r=4 时窗口连续收缩了两次。换成 if 只会收缩一次，留下一个有效但不是最短的窗口，悄无声息地返回 3 而不是 2。
求最长用 while (invalid) shrink;，之后再记录。求最短用 while (valid) { record; shrink; }。两个模式的区别就在这两行，其余代码完全一样。
代价： O(n)。lo 和 r 各自只遍历数组一次，所以嵌套循环仍然是线性的。
适用场景： 题目里出现最短、最小或最小长度，并且所有值都朝同一个方向推动那个量。最后这个条件很重要：数组里有负数时，扩大不再保证和变大，收缩规则就不成立了，这时要改用前缀和，也就是第 3 篇的内容。
模式 9 — 先数“至多”，相减得到“恰好”
统计恰好包含 K 个不同值的子数组个数。
直接滑动会卡住。如果窗口里不同的值太少，没有任何操作能修复：从左边收缩不可能增加种类。条件不是单向的，窗口就无从下手。
“至多 K 个”是单向的。不同的值太多，收缩总能修复。所以改数这个，数两次：
exactly K = (at most K) − (at most K−1)“至多 K 个”可以顺畅地滑动，因为不同的值太多时，从左边收缩就能修复。“恰好 K 个”不行，太少的情况没有任何操作能修复。所以把容易的数两次，再相减。
这个模式的另一半是计数本身。如果窗口 [lo..r] 有效，那么所有以 r 结尾、起点在 lo..r 之间的窗口也都有效，因为从左边丢掉元素只会让不同值的个数变少。这样的窗口有 r - lo + 1 个，一步加上，不用逐个枚举。
int[] a = [1, 2, 1, 2, 3];
int k = 2;
// Windows with AT MOST k distinct values. This one is easy to slide, because
// "too many distinct" is fixable by shrinking from the left.
static long AtMost(int[] a, int k, string label)
{
Dictionary<int, int> count = [];
long total = 0;
int lo = 0;
for (int r = 0; r < a.Length; r++)
{
count[a[r]] = count.GetValueOrDefault(a[r]) + 1;
while (count.Count > k)
{
if (--count[a[lo]] == 0) count.Remove(a[lo]);
lo++;
}
// Every window ending at r and starting at lo..r is valid: that is r-lo+1 of them.
total += r - lo + 1;
}
Console.WriteLine($"{label}: {total}");
return total;
}
long atMostK = AtMost(a, k, $"at most {k} distinct");
long atMostK1 = AtMost(a, k - 1, $"at most {k - 1} distinct");
Console.WriteLine($"\nexactly {k} distinct = {atMostK} - {atMostK1} = {atMostK - atMostK1}");输出：
at most 2 distinct: 12
at most 1 distinct: 5
exactly 2 distinct = 12 - 5 = 7代价： O(n) 做两次，仍然是 O(n)。
适用场景： 题目里出现恰好。恰好 K 个不同值、恰好 K 个奇数、和落在某个区间内，都属于这一类。做法永远一样：找到问题的单向版本，数两次，相减。
模式 10 — 窗口最大值，不用重新扫描
输出每个大小为 k 的窗口里的最大值。每个窗口重新扫描一遍是 O(nk)。用堆可以做到 O(n log k)，但要靠延迟删除来处理滑出窗口的值。
O(n) 的解法来自一个观察。如果 a[i] 比某个 a[j] 小，且 j > i，那么 a[i] 就出局了。以后任何包含 i 的窗口也都包含 j，而 j 更大，也更晚离开。a[i] 再也不可能成为最大值，所以根本不用保存它。
只保留仍有机会的候选值。从队头到队尾，它们是递减的。
双端队列里存的是索引，对应的值从队头到队尾始终递减。每个索引只入队一次、出队一次，所以尽管里面有 while 循环，整个扫描仍是 O(n)。
int[] a = [1, 3, -1, -3, 5, 3, 6, 7];
int k = 3;
LinkedList<int> dq = []; // holds INDICES, values decreasing front to back
List<int> answer = [];
for (int r = 0; r < a.Length; r++)
{
while (dq.Count > 0 && dq.First!.Value <= r - k)
{
Console.WriteLine($"r={r} index {dq.First.Value} fell out of the window drop from front");
dq.RemoveFirst();
}
while (dq.Count > 0 && a[dq.Last!.Value] <= a[r])
{
Console.WriteLine($"r={r} a[{dq.Last.Value}]={a[dq.Last.Value]} <= a[{r}]={a[r]} it can never win again, drop from back");
dq.RemoveLast();
}
dq.AddLast(r);
if (r >= k - 1)
{
answer.Add(a[dq.First!.Value]);
Console.WriteLine($"r={r} window [{r - k + 1}..{r}] deque=[{string.Join(",", dq)}] max = a[{dq.First.Value}] = {a[dq.First.Value]}");
}
}
Console.WriteLine($"\nmaxima: [{string.Join(", ", answer)}]");输出：
r=1 a[0]=1 <= a[1]=3 it can never win again, drop from back
r=2 window [0..2] deque=[1,2] max = a[1] = 3
r=3 window [1..3] deque=[1,2,3] max = a[1] = 3
r=4 index 1 fell out of the window drop from front
r=4 a[3]=-3 <= a[4]=5 it can never win again, drop from back
r=4 a[2]=-1 <= a[4]=5 it can never win again, drop from back
r=4 window [2..4] deque=[4] max = a[4] = 5
r=5 window [3..5] deque=[4,5] max = a[4] = 5
r=6 a[5]=3 <= a[6]=6 it can never win again, drop from back
r=6 a[4]=5 <= a[6]=6 it can never win again, drop from back
r=6 window [4..6] deque=[6] max = a[6] = 6
r=7 a[6]=6 <= a[7]=7 it can never win again, drop from back
r=7 window [5..7] deque=[7] max = a[7] = 7
maxima: [3, 3, 5, 5, 6, 7]有两个细节值得点明。第一，双端队列存的是索引而不是值，因为要检查队头是否已经滑出窗口，这是个关于位置的问题。第二，队头永远是答案：它是存活下来的最大候选值，原先排在它前面的元素，都因为比它小而被丢掉了。
嵌套的 while 循环看起来是平方级的，其实不是。每个索引恰好入队一次，最多出队一次，所以整个扫描的总工作量不超过 2n。
代价： 时间 O(n)，空间 O(k)。
适用场景： 需要在固定窗口上维护滑动的最小值或最大值。结构不变，把比较反过来，就得到滑动最小值。
要点
- 每个窗口重新计算，会把重叠部分扔掉。 改为用离开的值和进来的值修正当前结果，两次运算，而不是
k次。 - 最长和最短是同一份代码，只是
while放在不同位置。 最长：无效时收缩，然后记录。最短：有效时先记录再收缩。 lo永远不能往回走。 凡是让左边界跳过上一次出现位置的模式，都需要prev >= lo这个判断，"abba"是能证明这一点的最小输入。- “恰好 K 个”没法直接滑动。 太少的情况无法从左边修复。把“至多 K 个”数两次，再相减。
- 一个有效窗口
[lo..r]贡献r - lo + 1个子数组，而不是一个。逐个数窗口，是把线性解法写成平方级的另一种常见方式。 - 单调队列丢弃所有更小、更旧的值。 它存索引，队头就是答案，每个索引只进出一次，O(n) 的全部理由就在这里。
第 3 篇讲滑动窗口失灵时怎么办：负数、任意区间，以及对整段元素同时做更新。也就是前缀和与差分数组。