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;
}

复杂度

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

总结

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

目录

题意

思路

Python 知识

代码

复杂度

总结