02-双指针-A-B 数对

题目

链接：P1102 A-B 数对 - 洛谷

思路

问题场景想象

我们可以把这个问题想象成在一个排队的队伍里找符合特定身高差的人对。给定的数列里的每个数就好比队伍里每个人的身高，而差值 C 就是我们要找的身高差。我们的目标是找出队伍里所有身高差恰好是 C 的人对有多少组。

1. 排队整理（排序）

首先，我们让队伍里的人按照身高从小到大排好队。这样做的好处是，我们可以从矮到高依次去检查每个人，并且能很方便地知道后面的人肯定比前面的人高或者一样高。就好像我们从队伍的最前面开始，一个一个往后看，这样找身高差会更有规律。

2. 准备工作

• ans 就像是一个计数器，用来记录我们找到的符合身高差是 C 的人对的数量，一开始计数器归零。
• r1 和 r2 就像是我们的两只手指，都先指向队伍的第一个人。

3. 开始找人（双指针遍历）

• 外层循环（固定左指针 l）：
  • 我们让一个手指（左指针 l）从队伍的最前面开始，依次指向每一个人。这个手指指向的人就是我们要找的 “基准人”，也就是数对里的 B。
• 第一个 while 循环（移动 r1 指针）：
  • 另一只手指 r1 从队伍的第一个人开始往后移动。我们用 r1 指向的人的身高减去基准人的身高，如果这个差值小于 C，说明当前 r1 指向的人还不够高，和基准人的身高差没达到我们想要的 C，那就让 r1 继续往后指，直到找到一个人，他和基准人的身高差大于等于 C 为止。这个 r1 指向的人就是第一个和基准人身高差可能是 C 的人。
• 第二个 while 循环（移动 r2 指针）：
  • 再用另一只手指 r2 也从队伍第一个人开始往后移动。同样用 r2 指向的人的身高减去基准人的身高，如果这个差值小于等于 C，说明 r2 指向的人和基准人的身高差还在我们允许的范围内，那就让 r2 继续往后指，直到找到一个人，他和基准人的身高差大于 C 为止。这个 r2 指向的人的前一个人就是最后一个和基准人身高差是 C 的人。
• 统计人对数量：
  • 当我们确定了 r1 和 r2 的位置后，如果 r1 指向的人和基准人的身高差恰好是 C，并且 r2 前一个人（也就是 r2 - 1 指向的人）和基准人的身高差也恰好是 C，那就说明从 r1 到 r2 - 1 这些人都能和基准人组成身高差是 C 的人对。这些人对的数量就是 r2 - r1 个，我们把这个数量加到计数器 ans 里。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int q[N];
int main(){int n,c;cin>>n>>c;for(int i=1;i<=n;i++){cin>>q[i];}sort(q+1,q+n+1);//我们的数组是从第2个元素开始放的int r1=1,r2=1;long long ans=0;for(int l=1;l<=n;l++){while(r1<=n&&q[r1]-q[l]<c)r1++;//r1的目标是找到第一个等于差C的位置while(r2<=n&&q[r2]-q[l]<=c)r2++;//这里是<=;因为r2的目标是找到第一个超过差C的位置if(q[r1]-q[l]==c&&q[r2-1]-q[l]==c){ans+=r2-r1;}}cout<<ans<<endl;return 0;
}