题目描述

给出一串正整数数列以及一个正整数 $C$，要求计算出所有满足 $A - B = C$ 的数对的个数（不同位置的数字一样的数对算不同的数对）。

输入格式

输入共两行。

第一行，两个正整数 $N,C$。

第二行，$N$ 个正整数，作为要求处理的那串数。

输出格式

一行，表示该串正整数中包含的满足 $A - B = C$ 的数对的个数。

样例

样例输入

4 1
1 1 2 3

样例输出

3

这题目前我学到了map数组、二分、套用函数、双指针四种思路，首先C是已知的，我们可以选择对B或者对A展开循环，即将A或B其中一个固定去找另一个与之配对的元素，看有多少个或出现了多少次，逐一累加起来就能得到结果了。

C++代码如下：

map

这种方法一个让我不解的地方，如果不存在num[i]+c这个数，因为这个数没有被我初始化出现了多少次，那么a[num[i]+c]的值会默认是0还是什么？所以我感觉得确定一下边界，定义一个check函数检查一下这个数是否存在，不过我提交了这段是可以AC的，还是挺神奇的，再写的check函数又会增加时间复杂度，就没写了。

#include<iostream>
#include<map>
using namespace std;
int n,c;
long long ans;
map<int,int> a;
int num[200005];
int main()
{
    cin>>n>>c;
    for(int i=1;i<=n;i++)
    {
        cin>>num[i];
        a[num[i]]++;    //当前数的个数++ 
    }
    for(int i=1;i<=n;i++)
    {
        ans+=a[num[i]+c];    //答案+=相差为c的数的个数，即a[num[i]+c]位置的数的个数 
    }
    cout<<ans;
    return 0;
}

二分或者套用函数

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 200000;
int a[N];
int n, c;

int f1(int a[], int len, int x) {
    int l = -1, r = len;
    while (l + 1 < r) {
        int mid = l + r >> 1;
        if (a[mid] < x) {
            l = mid;
        } else {
            r = mid;
        }
    }
    if (a[r] == x) {
        return r;
    } else {
        return -1;
    }
}

int f2(int a[], int len, int x) {
    int l = -1, r = len;
    while (l + 1 < r) {
        int mid = l + r >> 1;
        if (a[mid] > x) {
            r = mid;
        } else {
            l = mid;
        }
    }
    if (a[l] == x) {
        return l;
    } else {
        return -1;
    }
}

int main() {
    cin >> n >> c;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    sort(a, a + n);
    long long cnt = 0; //数对可能涉及到数据的平方，需要开long long
    int s;
    for (int b = 0; b < n; b++) {
        if (b >= 1 && a[b] == a[b-1]) {  // 如果当前的数与前一个数相同，则直接将上一个数的计数器加到当前的计数器中
            cnt += s;
        } else {
            int x = a[b] + c;
            /*
            int* lb = lower_bound(a, a + n, x);  // 找到第一个大于等于 x 的元素的位置
            int* ub = upper_bound(a, a + n, x);  // 找到第一个大于 x 的元素的位置
            if (*lb == x && *(ub - 1) == x) {
                s = (ub - lb);
            } else {  //没找到该数
                s = 0;
            }
            这样就无需定义函数了*/
            int res1 = f1(a, n, x);
            if (res1 == -1) {
                s = 0;
            } else {
                int res2 = f2(a, n, x);
                s = res2 - res1 + 1;
            }
            cnt += s;
        }
    }
    cout << cnt;
    return 0;
} 

双指针

#include <iostream>
#include <cstdio> //输入数据较多建议使用scanf和printf代替cin和cout
#include <algorithm>
using namespace std;

const int N = 200000;
int x[N];
int n, c;

int main() {
    scanf("%d %d",&n,&c);
    for (int i = 0; i < n; i++) {
        scanf("%d",&x[i]);
    }
    sort(x, x + n);//首先让它变成有序数组
    long long cnt = 0;//总结果
    int s;//单个数的结果
    for(int a = 0,b1=0,b2=0; a < n ; a ++) {//看与A配对的B有多少个，求始末位置
        if (a>= 1 && x[a] == x[a-1]) {  //如果当前的数与前一个数相同，则直接将上一个数的计数器加到当前的计数器中
            cnt += s;
        } else {
            while(b1 <= a && x[a]-x[b1]>c ) b1 ++;//注意A、C不变，循环结束后刚好得出第一个B的位置
            while(b2 <= a && x[a]-x[b2]>=c) b2 ++;//注意这里循环结束后返回的是第一个比B大的元素的位置
            if(x[a] - x[b1] == c && x[a] - x[b2-1] == c){//确保这个位置是B，此外b2-1才是最后一个B
                s=b2-b1;//这里其实是b2-1-b1+1,根据刚刚的解释应该能理解吧
            }
            else{
                s=0;//没找到这个数，这个条件绝对绝对不能忘
            }
            cnt+=s;
        }
    }
    printf("%lld\n",cnt);////注意使用%lld输出long long类型的变量
    return 0;
} 

这也是算的最快的，如下图：