双指针与滑动窗口

一、暴力枚举的痛点：为什么要让指针“不走回头路”？

在数组中寻找满足特定条件的连续区间或数值对，最朴素的直觉永远是双层暴力循环：

外层循环固定左端点 $i$，内层循环枚举右端点 $j$，从头扫到尾。这样的代码谁都会写，但只要数据规模达到 $n = 10^5$ 或 $2 \times 10^5$，$O(n^2)$ 的时间复杂度必然会在评测机上收获一片惨红的 Time Limit Exceeded。

// 效率低下的暴搜模型：右端点机械地一次次重来
for (int i = 1; i <= n; i++) {
    for (int j = i; j <= n; j++) {
        // 每次都要重新拉扯一段区间检查条件...
    }
}

为什么暴力算法会慢？

核心劣势在于：每一次外层循环把左端点 $i$ 往右挪动一格时，内层循环的 $j$ 就彻底失忆，被迫重新回到起点打工。

暴力解法完全无视了上一轮枚举所积攒出来的所有状态信息。然而在很多问题中，当左端点 $i$ 改变时，满足条件的右端点 $j$ 是具备单调运动趋势的——它根本不需要回头。

双指针（Two Pointers）与滑动窗口的核心魔法，就是利用题目内在的单调性，让两个指针各自单向推进，永不后退。两个指针各自最多走 $n$ 步，将两层嵌套循环的时间复杂度直接降维打击到极其优美的 $O(n)$。

二、相向双指针：有序序列中的“两头包抄与降维排除”

相向双指针最经典的舞台，是在有序数组中寻找特定组合。

1. 物理视角的转换：两数之和

问题场景：给定一个单调非递减的有序整数序列，寻找两个不同位置的数，使得它们的和恰好等于目标值 $target$。

我们派出两个指针：

• 左指针 $l$ 指向序列最小值（最左端 $1$）。
• 右指针 $r$ 指向序列最大值（最右端 $n$）。

我们让两名哨兵向中间靠拢。面对当前的和 $sum = a[l] + a[r]$，决策逻辑极其干脆：

直观例子：对于有序数组 $[1, 2, 4, 7, 11]$，目标和 $target = 9$。

1. 初始状态：$l$ 指向 $1$，$r$ 指向 $11$。和为 $1 + 11 = 12 > 9$。$11$ 哪怕配最小的 $1$ 都太大了，永久丢弃 $11$，$r$ 左移指向 $7$。
2. 当前状态：$l$ 指向 $1$，$r$ 指向 $7$。和为 $1 + 7 = 8 < 9$。$1$ 哪怕配最大的 $7$ 都太小了，永久丢弃 $1$，$l$ 右移指向 $2$。
3. 当前状态：$l$ 指向 $2$，$r$ 指向 $7$。和为 $2 + 7 = 9$。命中目标！

每一次比较，我们都依据单调性彻底排除了整整一行/一列候选解。这才是双指针提速的本质所在：不是撞运气，而是严格的单调排除法。

2. 细节魔鬼：为什么循环条件必须是 l < r？

在考场上，千万不能把循环条件随手写成 while (l <= r)。

题目明确要求寻找两个不同位置的数。如果写成 l <= r，当 $target$ 恰好是偶数（比如 $8$），且数组中只有一个 $4$ 时，两个指针在 $4$ 的位置重合，程序就会误判“$4 + 4 = 8$”，把同一个元素盗用两次！

此外，负数的加入完全不会破坏这套逻辑——负数加负数依然保留大小单调序。但无序数组绝对不能直接这样搞。若数组无序，必须先排序；如果题目要求输出原序列的 1-based 下标，排序时还必须绑定原始编号（例如用 pair 或结构体）。

3. 完整程序 1：有序数组的两数之和

输入输出协议与范围：

• 第一行输入整数 $n$ 和目标值 $target$（$1 \le n \le 2 \times 10^5$，$|target| \le 2 \times 10^9$）。
• 第二行输入 $n$ 个单调非递减的整数 $a_i$（$|a_i| \le 10^9$）。
• 输出任意一对合法的 1-based 下标 $l, r$（满足 $l < r$）；若无解输出 -1。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=200005;

int n,target;
int a[N];

void solve(){
	cin>>n>>target;
	for(int i=1;i<=n;i++) cin>>a[i];
	
	int l=1,r=n;
	while(l<r){
		int sum=a[l]+a[r];
		if(sum==target){
			cout<<l<<" "<<r<<'\n';
			return;
		}
		if(sum<target) l++;
		else r--;
	}
	cout<<-1<<'\n';
}

signed main(){
	ios::sync_with_stdio(0),cin.tie(0);
	solve();
	return 0;
}

• 时间复杂度：左右指针每次判断必有一方移动一格，移动总次数严格不超过 $n - 1$ 次，复杂度为极其干净的 $O(n)$。
• 空间复杂度：除保存原序列外无额外开销，为 $O(n)$。

三、同向双指针（滑动窗口）：动态维护一段“活的状态”

如果说相向指针是“两面夹击”，那么同向指针就是“一人领跑、一人跟进”。

当左右指针同向而行时，区间 $[l, r]$ 在视觉上就像一扇在数组上滑行的动态窗口：

• 右端点 $r$：主动探索者。负责向右扩张，把新元素纳入窗口。
• 左端点 $l$：被动追随者。当窗口内的状态超标受损时，负责从左侧收缩吐出旧元素，直到窗口重新合法。

💡 核心教学法：千万不要把滑动窗口当成孤零零的两个下标！ 窗口内永远绑定着一份活的物理状态：它可以是区间和 sum、元素频次计数 cnt、或者是互不相同的元素种数。 右端进窗加状态，左端出窗扣状态。 进出必须对等，少扣一次，状态彻底报废！

1. 经典模型：非负序列中和不超过 $K$ 的最长连续段

问题场景：给定一个非负整数序列和一个阈值 $K$，求元素和不超过 $K$ 的最长连续子区间的长度。

手推演练：非负数组 $[2, 1, 3, 1, 1]$，$K = 4$。

1. $r = 1$：元素 $2$ 入窗，窗口 $[2]$，和为 $2 \le 4$。合法，长度 $1$。
2. $r = 2$：元素 $1$ 入窗，窗口 $[2, 1]$，和为 $3 \le 4$。合法，长度 $2$。
3. $r = 3$：元素 $3$ 入窗，此时窗口变成 $[2, 1, 3]$，和暴涨为 $6 > 4$，超标！
   • 左端点 $l$ 启动收缩：吐掉左边的 $2$，$l$ 移到位置 $2$；
   • 此时窗口恢复为 $[1, 3]$，和回落为 $4 \le 4$。合法，长度为 $3 - 2 + 1 = 2$。
4. $r = 4$：元素 $1$ 入窗，和变为 $4 + 1 = 5 > 4$，超标！
   • 左端吐掉 $1$，$l$ 移到位置 $3$；
   • 窗口变为 $[3, 1]$，和为 $4$。合法，长度 $2$。
5. $r = 5$：元素 $1$ 入窗，和变为 $4 + 1 = 5 > 4$，超标！
   • 左端吐掉 $3$，$l$ 移到位置 $4$；
   • 窗口变为 $[1, 1]$，和为 $2$。合法，长度 $2$。

整个扫描过程中，窗口合法的最大长度就是 $2$。

2. 深入本质：为什么左端点 $l$ 永远不需要向左倒退？

这里的数学基石是数组元素的非负性。

假设以当前 $r$ 为右端点时，由于区间和超过了 $K$，导致左端点 $l_0$ 被我们无情地抛弃了。 随着 $r$ 继续向后移动，新加入进来的数全是非负数（只会让总和越来越大，或者至少不减）。一个在之前就已经超标的左端点 $l_0$，在未来加入更多非负数后，更加不可能重新变合法！

既然 $l_0$ 已经注定万劫不复，我们就永远不需要回头看它一眼。

3. 致命易错：有负数时为什么滑动窗口当场暴毙？

如果数组中含有负数，比如序列 $[5, -4]$，限制 $K = 2$：

• 当走到 $5$ 时，和为 $5 > 2$，滑动窗口会判定超标，把 $5$ 丢掉；
• 但接下来遇到了 $-4$，总和变成了 $5 + (-4) = 1 \le 2$！
• 之前被我们丢弃的 $5$，因为后面负数的拯救，居然死而复生了！

警钟长鸣：一旦引入负数，区间和对端点的单调性彻底粉碎，滑动窗口立刻失效。带负数的区间和极值必须改用前缀和结合数据结构或单调栈来解，切忌生搬硬套。 如果问的是“和恰好为 $k$ 的子段有多少个”，可接着看《前缀和与差分》第六节的前缀和频次统计。

4. 复杂度推导：双层循环为什么是 $O(n)$？

看代码时，不少初学者被外层 for 和内层 while 吓退，以为这是 $O(n^2)$。

请注意物理运动轨迹：

• 右端点 $r$ 从 $1$ 走到 $n$，总共走了 $n$ 步；
• 左端点 $l$ 只能向右走，哪怕在内层 while 里拼命加，在整个程序生命周期里，它最多也只能前进 $n$ 步（一旦 $l > r$ 循环自然终止）。

两个指针各自单向奔跑，总步数加起来不超过 $2n$ 次。均摊复杂度是极其坚固的 $O(n)$。

5. 完整程序 2：非负序列的最长限和窗口

输入输出协议与范围：

• 第一行输入 $n$ 和上限 $K$（$1 \le n \le 2 \times 10^5$，$0 \le K \le 10^{18}$）。
• 第二行输入 $n$ 个非负整数 $a_i$（$0 \le a_i \le 10^9$）。
• 输出满足区间和不超过 $K$ 的最长连续子区间的长度；若不存在合法区间则输出 $0$。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=200005;

int n,k;
int a[N];

void solve(){
	cin>>n>>k;
	for(int i=1;i<=n;i++) cin>>a[i];
	
	int l=1,ans=0,sum=0;
	for(int r=1;r<=n;r++){
		sum+=a[r]; // 右端扩张：状态进窗
		
		// 状态超标：左端持续收缩，直到重新合法或窗口变空
		while(sum>k){
			sum-=a[l]; // 左端收缩：状态出窗
			l++;
		}
		
		// 此时 [l, r] 必为以 r 结尾的最长合法段
		ans=max(ans,r-l+1);
	}
	cout<<ans<<'\n';
}

signed main(){
	ios::sync_with_stdio(0),cin.tie(0);
	solve();
	return 0;
}

• 时间复杂度：左右端点单向滑动，均为 $O(n)$。
• 空间复杂度：$O(n)$。

四、进阶状态维护：频次数组看门的“最长无重复段”

滑动窗口维护的状态，不仅可以是区间数值之和，还可以是元素的频次分布。

1. 灵魂数组：cnt 计数看门人

问题场景：给定一个长度为 $n$ 的正整数序列，寻找一段最长的连续区间，使得区间内的所有数字互不相同。

我们引入全局频次数组 cnt[x]，它的物理意义是：数值 $x$ 在当前窗口 $[l, r]$ 内出现的次数。

当右端点推进到 $r$ 时，我们执行 cnt[a[r]]++。此时，窗口内唯一可能产生冲突的嫌疑犯，只有刚刚进窗的这名新成员 $a[r]$！

因为在 $a[r]$ 进窗之前，窗口 $[l, r-1]$ 已经被我们千锤百炼打造成了一个完全无重复的纯净区间。所以我们根本不需要扫描整个频次表，只需要死死盯着 cnt[a[r]]：

• 若 cnt[a[r]] > 1，说明发生了撞车；
• 此时驱动左指针 l 疯狂出窗：cnt[a[l]]--, l++；
• 一直缩到把前面那个相同的数字踢出窗外，使 cnt[a[r]] 回落到 $1$ 为止。

直观例子：处理序列 $[1, 2, 1, 3, 2]$。

• $r = 1 \dots 2$：窗口 $[1, 2]$，无重复；
• $r = 3$：新进数字 $1$。cnt[1] 变成 $2$。左端开始踢人：踢掉第一个 $1$ 后，cnt[1] 降为 $1$。窗口变为 $[2, 1]$，合法！
• 随后进 $3$：窗口 $[2, 1, 3]$，长度达到 $3$；
• 进 $2$：cnt[2] 暴增为 $2$。左端开始踢：先踢 $2$，cnt[2] 立即降回 $1$。窗口变为 $[1, 3, 2]$，长度仍为 $3$。最终答案锁定为 $3$。

2. 完整程序 3：最长无重复连续段

输入输出协议与范围：

• 第一行输入 $n$（$1 \le n \le 2 \times 10^5$）。
• 第二行输入 $n$ 个整数 $a_i$（$0 \le a_i \le 10^6$）。
• 输出序列中最长无重复元素的连续子区间长度。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=200005;
const int V=1000005;

int n;
int a[N],cnt[V];

void solve(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	
	int l=1,ans=0;
	for(int r=1;r<=n;r++){
		cnt[a[r]]++; // 新数进窗，频次增加
		
		// 只要刚刚进窗的数发生冲突，就持续从左侧驱逐
		while(cnt[a[r]]>1){
			cnt[a[l]]--; // 移出左端数字，频次扣除
			l++;
		}
		
		ans=max(ans,r-l+1);
	}
	cout<<ans<<'\n';
}

signed main(){
	ios::sync_with_stdio(0),cin.tie(0);
	solve();
	return 0;
}

• 值域陷阱提醒：本题数据范围给出 $a_i \le 10^6$，所以直接开全局数组 cnt[1000005] 是最轻快的解法。但如果题目给出 $a_i \le 10^9$，就绝对不能无脑开数组，否则考场瞬间内存超限（MLE）。此时可以先进行离散化，将稀疏的大权值映射到 $[1, n]$ 的连续排名上，再跑滑动窗口，具体做法见《离散化》。

五、认知升维：滑动窗口与单调队列的本质边界

很多竞赛新手容易把“滑动窗口”和“单调队列”两个名词混淆。我们必须在物理机制上把它俩彻底拆开。

1. 为什么“区间最大值”不能只靠普通滑动窗口？

回顾前面的例题，滑动窗口之所以能轻巧维护状态，是因为维护的属性具备可逆性（消去性）：

• 区间和：新进一个数执行 sum += a[r]，移出一个数执行 sum -= a[l]。
• 频次表：新进一个数执行 cnt[x]++，移出一个数执行 cnt[x]--。

但是，如果题目要求你维护固定长度 $K$ 的窗口内的最大值呢？

试想：窗口里原本是 $[5, 2, 4]$，最大值显然是 $5$。当窗口向右滑到 $[2, 4, 3]$ 时，$5$ 离开了窗口。 你只知道“老大哥 $5$ 走了”，但你能像减法一样直接把 $5$ 从状态里减掉，算出剩下的 $2, 4$ 谁最大吗？

做不到！最大值这个运算是不可逆的。一旦原本的最大值离开，剩余元素的极大值完全无法还原。

2. 两者的神仙配合

• 滑动窗口：决定了当前区间的合法范围 $[l, r]$（管理谁在有效期内）。
• 单调队列：在窗口滑动的基础上，利用单调性维护极值的候选池（淘汰那些“既比你老、又比你弱”的废柴元素）。

滑动窗口是外框机制，单调队列是其内部处理不可逆极值查询时的特化数据结构。两者不是对立的替代品，而是协作关系。 具体实现见《单调队列思想》。

六、变形与发散：同一扇窗口下的问法转换

掌握了滑动窗口的基本架构后，出题人常常只改动一两个字，考查学生对状态维护的深层理解。

1. 变式 A：从“求最长长度”到“数一数有多少个区间”

问题：求有多少个连续子区间，其元素和不超过 $K$？（数组非负）

在程序 2 中，我们每找到一个合法的以 $r$ 结尾的窗口 $[l, r]$，只记录了它的长度 $r - l + 1$。 仔细思考：既然窗口 $[l, r]$ 里的所有元素和都 $\le K$，且数组非负，那么该窗口内部以 $r$ 结尾的所有子后缀区间，和必然也全部 $\le K$！

• 满足条件的区间包括：$[l, r], [l+1, r], \dots, [r, r]$。
• 这样的合法区间恰好有 $r - l + 1$ 个！

因此，我们只需要把求最大值的 ans = max(ans, r - l + 1)，改成累加器：

2. 变式 B：从“不超过 K 的最长”到“至少为 S 的最短”

问题：求元素和至少为 $S$ 的最短连续子区间的长度。

此时双指针的收缩逻辑被完美翻转：

• 右端点 $r$ 向右扩张，直到窗口和第一次达到或超过 $S$；
• 一旦达标，说明当前窗口是一个合法解，先尝试用当前长度更新答案：ans = min(ans, r - l + 1)；
• 随后尝试主动收缩左端点：sum -= a[l], l++，试探在更短的长度下是否依然能维持 $\ge S$ 的和；
• 缩到不再满足 $\ge S$ 为止，再让 $r$ 继续向右找补。

注意结算时机：满足条件时边缩边更新最小答案，而不是等缩完出界后再更新。

七、跨序列协同：两个有序数组的归并式双指针

这就是归并排序中的合并一步，也可以对照《排序算法进阶》阅读。

前面讨论的相向双指针，两个哨兵是在同一个序列的首尾向中间包抄。而在算法竞赛中，还有一类极高频的经典场景：我们手头有两个各自已经单调非递减的独立序列 $A$ 和 $B$。

此时，若把两个序列拼在一起重新调用 std::sort，时间开销是 $O((n+m) \log(n+m))$。但只要利用好两个序列各自已具备的有序性，派出两个同向推进的指针分别看守两个序列的队头，我们就能在 $O(n+m)$ 的线性时间内完成整合。这就是归并式双指针（Merge-style Two Pointers）。

1. 物理推导与决策逻辑

问题场景：给定两个非递减有序数组 $A$（长度 $n$）和 $B$（长度 $m$），将它们合并为一个整体有序的数组 $C$（长度 $n+m$）。

我们派出指针 $i$ 监视 $A$ 的当前未决头部，指针 $j$ 监视 $B$ 的当前未决头部：

• 在当前时刻，$A[i]$ 是数组 $A$ 中剩余的所有数里的最小值；
• 同理，$B[j]$ 是数组 $B$ 中剩余的所有数里的最小值。

这意味着：全局剩余的所有未选元素中，最小的那个数必定在 $A[i]$ 与 $B[j]$ 之间产生！ 我们根本不需要扫描后面的任何元素，只要直接对比它俩即可：

当其中一个数组被率先掏空时，另一个数组剩余的元素必定全都不小于已合并的所有元素，且自身已有序，直接整段打包追加到末尾即可。

手算演练：$A = [1, 4, 7, 8]$，$B = [2, 3, 7]$。

1. 比较 $A[1]=1$ 与 $B[1]=2$：$1 \le 2$，取 $1$ 入队，$i$ 移至位置 $2$；
2. 比较 $A[2]=4$ 与 $B[1]=2$：$4 > 2$，取 $2$ 入队，$j$ 移至位置 $2$；
3. 比较 $A[2]=4$ 与 $B[2]=3$：$4 > 3$，取 $3$ 入队，$j$ 移至位置 $3$；
4. 比较 $A[2]=4$ 与 $B[3]=7$：$4 \le 7$，取 $4$ 入队，$i$ 移至位置 $3$；
5. 比较 $A[3]=7$ 与 $B[3]=7$：$7 \le 7$，取 $A$ 的 $7$ 入队，$i$ 移至位置 $4$；
6. 比较 $A[4]=8$ 与 $B[3]=7$：$8 > 7$，取 $B$ 的 $7$ 入队，$j$ 移出边界，$B$ 耗尽；
7. 将 $A$ 剩下的 $8$ 直接追加进队。最终合成 $[1, 2, 3, 4, 7, 7, 8]$。

2. 核心延伸：有序数组求公共交集

归并双指针的精髓不仅在于合并，还在于高效求交集。如果题目要求找出两序列中所有共同出现的数字：

• 若 $A[i] == B[j]$：说明发现共同元素，记入答案，随后两指针同时右移 i++, j++；
• 若 $A[i] < B[j]$：当前较小的 $A[i]$ 在 $B$ 中往后绝不可能配对成功（因为 $B$ 后面的数更大），果断 i++ 单向丢弃；
• 若 $A[i] > B[j]$：同理丢弃较小的 $B[j]$，执行 j++。

每一步比较至少让一个指针前进一格，同样严格保证 $O(n+m)$ 跑完全程，杜绝无意义的回头扫描。

3. 完整程序 4：双有序数组的线性归并

输入输出协议与范围：

• 第一行输入整数 $n, m$（$1 \le n, m \le 10^5$），分别表示数组 $A$ 和 $B$ 的长度。
• 第二行输入 $n$ 个单调非递减整数 $a_i$（$|a_i| \le 10^9$）。
• 第三行输入 $m$ 个单调非递减整数 $b_j$（$|b_j| \le 10^9$）。
• 输出一行共 $n+m$ 个整数，表示合并后的单调非递减新序列，数与数之间用空格隔开。

样例输入：

4 3
1 4 7 8
2 3 7

样例输出：

1 2 3 4 7 7 8

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=100005;

int n,m;
int a[N],b[N],c[N*2];

void solve(){
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=m;i++) cin>>b[i];
	
	int i=1,j=1,k=0;
	while(i<=n && j<=m){
		if(a[i]<=b[j]) c[++k]=a[i++];
		else c[++k]=b[j++];
	}
	while(i<=n) c[++k]=a[i++];
	while(j<=m) c[++k]=b[j++];
	
	for(int p=1;p<=k;p++){
		cout<<c[p]<<(p==k?'\n':' ');
	}
}

signed main(){
	ios::sync_with_stdio(0),cin.tie(0);
	solve();
	return 0;
}

• 时间复杂度：两指针单向递增，循环总推进次数为 $n+m$，复杂度为极其严格的 $O(n+m)$。
• 空间复杂度：存储结果数组需 $O(n+m)$。

八、滑窗频次维护的关键实现：多字符模式与 $O(1)$ 匹配指示器

在“最长无重复段”中，我们只需要防范“单个元素频次是否超过 $1$”，因此只需在 $a[r]$ 进窗后盯死 cnt[a[r]] > 1 这一个位置。

但在实际比赛中，经常会遇到更复杂的多元素频次匹配。例如：给定主串 $S$ 和模式串 $P$，要求在 $S$ 中寻找包含 $P$ 中所有字符（且各类字符出现频次均不低于 $P$ 中要求）的最短连续子串。

1. 为什么大字符集下不能每步遍历频次表？

很多同学在写这类题目时，虽然滑动窗口框架搭对了，但每当右指针右移或左指针收缩时，都会写一个长达 26 格（或甚至更大字符集）的循环去遍历比对：

// 仅示意全盘检查：依赖已维护的 win_cnt、need_cnt，字符编号为 0~25
bool check() {
    for (int c = 0; c < 26; c++) {
        if (win_cnt[c] < need_cnt[c]) return false;
    }
    return true;
}

在字符集较小（如 26 个小写字母）时，每次判断耗时 26 次操作，完全可以使用。但如果字符集扩大到 ASCII 全集（128/256），或者数组元素多达 $10^5$ 种，这种全盘检查会让总时间复杂度暴增为 $O(n \cdot |\Sigma|)$，滑窗原本优雅的线性优势会大打折扣。

2. 破局关键：维护“达标种类指示器” match

面对大字符集，我们不需要每次傻傻地核对所有种类，而应该利用增量思维，引入一个全局整型变量 match：

• 物理含义：当前窗口内，出现频次已经达到或超过目标要求的字符种类数。
• 目标状态：设模式串中总共出现了 $K$ 种不同的字符（记为 need_kinds）。当且仅当 match == need_kinds 时，当前窗口完全合法！

这样，原本需要检查全表的判定，在瞬间被降维成了单个变量的 $O(1)$ 整数比对。

3. 进窗与出窗的精准原子操作

为了让 match 不虚高、不漏记，必须在频次刚好跨越阈值的那一瞬间进行原子触发：

// 核心实现骨架：双指针进出窗时的精确状态维护
// need[x]：目标模式串对字符 x 的最低需求频次
// win[x]：当前滑窗内字符 x 的实际保有量
// need_kinds：模式串包含的互不相同的字符总种类数

// 1. 右端点进窗：元素 s[r] 加入窗口
int in_ch = s[r];
if (need[in_ch] > 0) { // 属于被考核的目标字符
    win[in_ch]++;
    if (win[in_ch] == need[in_ch]) {
        // 恰好在这一刻达标！达标种类数 +1
        match++;
    }
}

// 2. 当窗口完全达标（match == need_kinds）时，尝试收缩左端点以求最优解
while (match == need_kinds) {
    // 用当前窗口 [l, r] 结算答案（例如更新最小长度）
    
    int out_ch = s[l];
    if (need[out_ch] > 0) {
        if (win[out_ch] == need[out_ch]) {
            // 移出它后频次将不再达标，提前将达标种类数 -1
            match--;
        }
        win[out_ch]--;
    }
    l++; // 左端点收缩
}

直观小例子：需求为 a: 2 次，b: 1 次，总达标种类 need_kinds = 2。

• 窗口内 a 从 $1$ 涨到 $2$ 的瞬间，触发 match++；
• 窗口内 a 继续从 $2$ 涨到 $3$ 时，条件依然满足，但不触发 match 变动（避免重复记数）；
• 窗口收缩时，a 从 $3$ 跌到 $2$，依然达标，match 不变；
• 直到 a 从 $2$ 跌破为 $1$ 的前一刻，触发 match--，窗口重归不达标状态。

这种只在“临界跃迁点”更新指示器的技巧，是滑动窗口维护复杂多重频次状态的标准规范姿势。

九、转化单调性：恰好 $K$ 种不同数的差分转化思想

在很多高阶计数题中，出题人会给出这样的要求：“求有多少个连续子区间，其内部包含的不同数字恰好等于 $K$ 种”。

1. 认知障碍：为什么“恰好 $K$ 种”无法用单指针直接滑窗？

滑动窗口能维持 $O(n)$ 均摊复杂度的命根子，是区间条件的单调性。

• 如果条件是**“至多 $K$ 种不同数”**：

  • 右端点 $r$ 向右扩张，窗口内的数字种类数只增不减；
  • 一旦种类数超标（$> K$），左端点 $l$ 开始向右收缩，种类数只减不增，必然能收缩到刚好合法；
  • 此时对于固定的 $r$，所有合法的左端点构成了一个连续的闭区间 $[l, r]$，具有单调的极值边界。

• 但如果条件变成了**“恰好 $K$ 种不同数”**：

  • 满足“恰好 $K$ 种”的合法左端点并不只是一个极值点，而是构成了一段连续的区间。
  • 单纯的一个左端点指针无法直接同时圈定并维护这一整个合法的起点区间。

2. 破局之道：差分容斥转化

既然“至多”具备极佳的单调性，我们能否用“至多”来表达“恰好”？

答案极其优美：

• 设 $S_{\le K}$ 为包含不同数字种类不超过 $K$ 种的所有连续子区间的集合；
• 设 $S_{\le K-1}$ 为包含不同数字种类不超过 $K-1$ 种的所有连续子区间的集合。

显然，包含种类数不超过 $K-1$ 的区间，其种类数必然也同时满足不超过 $K$。因此在集合上存在严格的包含关系：

而包含种类恰好等于 $K$ 的区间，正是“至多 $K$ 种”中剔除掉“至多 $K-1$ 种”后剩下的纯粹部分！

转化为区间计数，立刻得到极为霸道的差分公式：

💡 核心数学转化： 把一个不具备单调性的等号匹配问题，拆解为两次完全具备单调性的不等式滑动窗口！ 我们只需要封装一个通用的 at_most(k) 滑窗计数函数，主函数直接跑一次 at_most(K) - at_most(K - 1)，就能降维解决问题。

3. 手算演练：差分法数区间

对于序列 $[1, 2, 1, 2, 3]$，统计恰好包含 $2$ 种不同数的连续子区间总数。

第一步：计算 at_most(2)（种类数 $\le 2$ 的区间数）

• $r = 1$（元素 $1$）：窗口 $[1]$，种数 $1 \le 2$。合法左端点可取 $1$。贡献 $1 - 1 + 1 = 1$ 个（即 $[1]$）；
• $r = 2$（元素 $2$）：窗口 $[1, 2]$，种数 $2 \le 2$。合法左端点可取 $1, 2$。贡献 $2 - 1 + 1 = 2$ 个（$[1, 2], [2]$）；
• $r = 3$（元素 $1$）：窗口 $[1, 2, 1]$，种数 $2 \le 2$。贡献 $3 - 1 + 1 = 3$ 个；
• $r = 4$（元素 $2$）：窗口 $[1, 2, 1, 2]$，种数 $2 \le 2$。贡献 $4 - 1 + 1 = 4$ 个；
• $r = 5$（元素 $3$）：元素 $3$ 入窗，种类变为 $3 > 2$，超标！
  • 左端踢 $a[1]=1$：窗口剩 $[2, 1, 2, 3]$，种类依然是 $3$（因为位置 $3$ 还有 $1$）；
  • 左端踢 $a[2]=2$：窗口剩 $[1, 2, 3]$，种类依然是 $3$；
  • 左端踢 $a[3]=1$：此时 $1$ 彻底清零，窗口收缩为 $[2, 3]$，种类降为 $2$！左端点停在 $l = 4$。
  • 贡献以 $r=5$ 结尾且左端点在 $[4, 5]$ 内的区间，共 $5 - 4 + 1 = 2$ 个（$[2, 3], [3]$）。
• 总计：at_most(2) $= 1 + 2 + 3 + 4 + 2 = 12$ 个。

第二步：计算 at_most(1)（种类数 $\le 1$ 的区间数，即纯单一数值段）

• $r = 1$：$[1]$，贡献 $1$ 个；
• $r = 2$：进 $2$ 超标，缩至 $[2]$，贡献 $1$ 个；
• $r = 3$：进 $1$ 超标，缩至 $[1]$，贡献 $1$ 个；
• $r = 4$：进 $2$ 超标，缩至 $[2]$，贡献 $1$ 个；
• $r = 5$：进 $3$ 超标，缩至 $[3]$，贡献 $1$ 个；
• 总计：at_most(1) $= 1 + 1 + 1 + 1 + 1 = 5$ 个。

第三步：差分做差

我们人脑暴力核对所有恰好 2 种的区间：

• 长度 2 的有：$[1, 2], [2, 1], [1, 2], [2, 3]$，共 $4$ 个；
• 长度 3 的有：$[1, 2, 1], [2, 1, 2]$，共 $2$ 个；
• 长度 4 的有：$[1, 2, 1, 2]$，共 $1$ 个。
• 长度 5 的区间 $[1, 2, 1, 2, 3]$ 包含 3 种数，不符合。
• 实际总数：$4 + 2 + 1 = 7$ 个。两者完全吻合！

4. 完整程序 5：恰好 $K$ 种不同数的子区间计数

输入输出协议与范围：

• 第一行输入整数 $n, K$（$1 \le K \le n \le 10^5$）。
• 第二行输入 $n$ 个整数 $a_i$（$0 \le a_i \le 10^5$）。
• 输出一个整数，表示包含恰好 $K$ 种不同数的连续子数组个数。

样例输入：

5 2
1 2 1 2 3

样例输出：

7

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=100005;

int n,k;
int a[N],cnt[N];

// 统计不同数字种类数不超过 limit 的子区间总数
int at_most(int limit){
	if(limit<=0) return 0;
	
	// 精准清空本次出现的频次，维持 O(n) 的高效清空
	for(int i=1;i<=n;i++) cnt[a[i]]=0;
	
	int l=1,types=0,res=0;
	for(int r=1;r<=n;r++){
		if(cnt[a[r]]==0) types++;
		cnt[a[r]]++;
		
		// 种类超标时收缩左端点
		while(types>limit){
			cnt[a[l]]--;
			if(cnt[a[l]]==0) types--;
			l++;
		}
		
		// 以 r 结尾、左端点在 [l, r] 的所有子区间种类数均 <= limit
		res+=(r-l+1);
	}
	return res;
}

void solve(){
	cin>>n>>k;
	for(int i=1;i<=n;i++) cin>>a[i];
	
	// 差分神技：恰好 K = 至多 K - 至多 (K - 1)
	cout<<at_most(k)-at_most(k-1)<<'\n';
}

signed main(){
	ios::sync_with_stdio(0),cin.tie(0);
	solve();
	return 0;
}

• 时间复杂度：函数 at_most 被调用两次，每次扫描指针单调推进，清空频次表也为 $O(n)$，整体时间复杂度为严格的 $O(n)$。
• 空间复杂度：全局频次数组与数据序列开销为 $O(n)$。

十、三指针法：单次扫描捕获“恰好 $K$ 种”的区间双界（选学）

💡 先修要求：熟练掌握同向双指针及差分转化思想。

在上面的差分模型中，我们调用了两次 at_most，实际上遍历了两遍数组。有没有办法只遍历一遍数组，直接在一趟扫描内求出答案呢？

答案是：三指针法（一个右探针，两个左哨兵）。

1. 双界区间分布的物理本质

对于任意固定的右端点 $r$，如果以 $r$ 结尾的子区间中存在恰好含 $K$ 种数的区间，那么这些合法的左端点 $l$ 必然落在一段连续的区间范围 $[l_1, l_2)$ 内：

• 最左合法边界 $l_1$：使得窗口 $[l_1, r]$ 包含的不同数种类刚好不超过 $K$ 的最远左边界（再往左挪一格，种类就会变成 $K+1$）；
• $l_2$：合法左端点区间右侧的第一个位置。它是使窗口 $[l_2, r]$ 包含的不同数种类刚好不超过 $K-1$ 的最远左边界（再往左挪一格，种类就会恰好达到 $K$）。

这意味着：当左端点 $l$ 处于 $[l_1, l_2)$ 之间时，区间 $[l, r]$ 内的不同数字种类严格等于 $K$！以 $r$ 结尾的合法区间个数，恰好就是 $l_2 - l_1$。

2. 状态推进要点

我们派出三个指针：

• 右指针 $r$：主动右移遍历数组；
• 左指针 $l_1$：配合全局计数器维护“不超过 $K$ 种”的极值左边界；
• 左指针 $l_2$：配合另一组计数器维护“不超过 $K-1$ 种”的极值左边界。

随着 $r$ 的右移，$l_1$ 与 $l_2$ 各自具备独立的单调递增性，两者都绝不需要回头。每移动一次 $r$，累加器直接执行 ans += (l2 - l1)。这种写法将差分的两趟过程压缩合并到单次循环内，在数据量极大且常数卡得很紧的高水平竞赛中是一把极具威力的手术刀。

十一、渐进式实战练习题单

第一阶段：问法转换与区间计数

1. 自定义实战 1：限和区间的组合计数
   • 问题描述：输入非负序列与上限 $K$（数据范围同程序 2），求和不超过 $K$ 的非空连续区间总个数。例如 $[1, 2, 1]$ 与 $K = 3$，答案为 $5$（区间为 $[1], [2], [1], [1, 2], [2, 1]$）。
   • 训练指引：将窗口更新逻辑改为累加 ans += (r - l + 1)。特别警惕：区间总数最坏可达 $n(n+1)/2 \approx 2 \times 10^{10}$，累加变量 ans 必须使用 long long，否则考场上直接爆 int 见祖宗。

第二阶段：收缩逻辑的逆向推演

2. 自定义实战 2：和至少为 $S$ 的最短子区间
   • 问题描述：给定非负整数数组与正整数 $S$（$n \le 2 \times 10^5, a_i \le 10^9, S \le 10^{18}$），求和至少为 $S$ 的最短非空连续区间长度。无解输出 $0$。例如序列 $[2, 1, 3, 1]$ 与 $S = 4$，最短合法段为 $[1, 3]$ 或 $[3, 1]$，输出 $2$。
   • 训练指引：循环体内使用 while(sum >= S)。牢记“进窗满足即更新，随后扣除左端继续试”的节奏，体会与最长限和段在收缩时机上的微妙对偶性。

第三阶段：复合状态的频次维护

3. 自定义实战 3：最多包含 $K$ 种不同数的最长连续段
   • 问题描述：给定序列与正整数 $K$（$1 \le K \le n \le 2 \times 10^5, 0 \le a_i \le 10^6$），求最多包含 $K$ 种不同元素的最长连续段长度。例如 $[1, 2, 1, 3, 2]$ 与 $K = 2$，输出 $3$（区间可取 $[1, 2, 1]$）。
   • 训练指引：除了维护频次表 cnt 外，额外维护一个整型变量 types 表示当前窗口内不同数字的种数。当某个元素进窗使其频次由 $0$ 变 $1$ 时，types++；当某个元素出窗使其频次由 $1$ 降为 $0$ 时，types--。收缩条件为 while(types > K)。

💡 教练的终局验收标准： 走出考场前，请在草稿纸上拿这句铁律反复质问自己： “我每一次移动指针，究竟利用单调性排除了哪些不可能的答案？” 能用数学物理推导回答清楚这句话，双指针才真正刻进了你的潜意识里。