A-B 数对

题意

统计有多少对不同位置上的数满足 $A-B=C$ 。相同数值出现在不同位置时，要分别计数。

思路

把等式改写为 $A=B+C$ 。若数值 B 出现 cnt[B] 次，数值 B+C 出现 cnt[B+C] 次，它们能组成的有序位置数对就是两者乘积。

因此只需统计频率，再对每种 B 累加：

\operatorname{cnt}[B]\times\operatorname{cnt}[B+C]

C 为正数，所以一对数值只会按较小值 B 统计一次。

Python 知识

collections.Counter 直接把序列变成“数值到出现次数”的映射。
访问不存在的键时，Counter[key] 返回 0，无需单独判断 B+C 是否出现。
sum(...) 配合生成器完成乘积聚合，不创建中间列表。
/home/rainboy/mycode/hugo-blog/content/program_language/python/collections_toolkit.md：Counter 的频率统计模式。
/home/rainboy/mycode/hugo-blog/content/program_language/python/generator_expression.md：生成器与 sum 的惰性聚合。

代码

python

1
2
3
4
5
6
7
8
9import sys
from collections import Counter


data = list(map(int, sys.stdin.buffer.read().split()))
n, difference = data[:2]
counts = Counter(data[2:2 + n])

print(sum(count * counts[value + difference] for value, count in counts.items()))

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42/**
 * Author by Rainboy blog: https://rainboylv.com github: https://rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-27 00:00
 * update_at: 2026-07-27 00:00
 */

/* P1102 A-B 数对 */
/* 排序后，对每个 a[i] 统计有多少 a[j] == a[i] + C。 */

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 200005;

int n, c;
int a[MAXN]; // 输入数组

int main() {
    cin >> n >> c;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    // 先排序
    sort(a + 1, a + n + 1);

    long long ans = 0;
    // 对每个 a[i]，找 a[i] + c 的出现次数
    int j = 1, k = 1;
    for (int i = 1; i <= n; i++) {
        // 用两个指针分别找等于 a[i]+c 的第一个和最后一个位置
        while (j <= n && a[j] < a[i] + c) j++;
        while (k <= n && a[k] <= a[i] + c) k++;
        // a[i]+c 的出现次数 = k - j
        ans += k - j;
    }

    cout << ans << "\n";
    return 0;
}

另一种写法：排序后用二分查找统计每个 B 对应的 B+C 出现次数。

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-08-01 02:00
 * update_at: 2026-08-01 02:00
 */

/* P1102 A-B 数对 */
/* 排序后，对每个 a[i] 用二分查找统计 a[i]+C 的出现次数。 */

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 200005;
const long long INF = 1e18; // 哨兵值，保证 bs_find 一定能找到答案

int n;
long long c;
long long a[MAXN]; // 输入数组，排序后使用；a[n+1]=INF 作为哨兵

int mid(int l,int r) {
    return (l+r) >> 1; //这是最快的写法
}

//检查pos位置的值是否符合要求
bool check(int pos,long long val){
    return a[pos] >= val;
}

//bs_find = binary search find
//返回 [l,r] 中第一个满足 a[pos] >= val 的位置，找不到返回 r
int bs_find(int l,int r,long long val) {
    while( l < r) {
        int m = mid(l,r);
        if( check(m,val)) //成立
            r = m;
        else //不成立,抛弃左半边
            l = m+1;
    }
    return l ;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> c;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    // 先排序
    sort(a + 1, a + n + 1);
    a[n + 1] = INF; // 哨兵，使二分查找找不到目标时能返回 n+1

    long long ans = 0;
    // 对每个 B = a[i]，用二分找 A = a[i]+c 的个数
    for (int i = 1; i <= n; i++) {
        long long target = a[i] + c; // 要找的 A
        // 等于 target 的元素个数 = 第一个 >= target+1 的位置 - 第一个 >= target 的位置
        int left = bs_find(1, n + 1, target);
        int right = bs_find(1, n + 1, target + 1);
        ans += right - left;
    }

    cout << ans << "\n";
    return 0;
}

复杂度

统计和遍历不同数值的期望时间复杂度为 $O(n)$ ，空间复杂度为 $O(n)$ 。

总结

题目强调“不同位置”，所以不能只判断数值是否存在。频率乘积恰好把两边所有位置组合完整计入答案。

目录

题意

思路

Python 知识

代码

复杂度

总结