洛谷P1102题解：A-B数对问题的高效解法

一、问题描述

给定N个整数和一个整数C，要求统计所有满足A-B=C的数对(A,B)的数量。其中A和B都是给定数组中的元素，且位置可以相同。

二、算法核心思想

1. 哈希表统计：使用unordered_map统计每个数字出现的次数

2. 线性扫描：遍历数组，对每个元素A，查找满足B=A-C的元素B的数量

3. 累加结果：将所有满足条件的B的数量累加得到最终结果

三、完整代码实现（带详细注释）

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

const int MAXN = 2e5 + 5;  // 定义最大数组大小
long long nums[MAXN];      // 存储输入数字的数组

int main() {
    int n;                 // 数字个数
    long long c;           // 目标差值C
    cin >> n >> c;         // 输入n和c
    
    // 使用哈希表统计每个数字出现的次数
    unordered_map<long long, int> countMap;
    for(int i = 0; i < n; i++) {
        cin >> nums[i];            // 读取数字
        countMap[nums[i]]++;       // 统计该数字出现次数
    }
    
    long long res = 0;             // 初始化结果计数器
    for(int i = 0; i < n; i++) {
        long long target = nums[i] + c;  // 计算需要的B值(A-B=C => B=A-C)
        res += countMap[target];         // 累加满足条件的B的数量
    }
    
    cout << res << endl;           // 输出结果
    return 0;
}

四、算法分步解析

1. 输入处理：

• 读取数字个数n和目标差值c

• 定义足够大的数组存储输入数字

2. 统计频率：

• 使用unordered_map统计每个数字出现的次数

• 哈希表的平均插入和查询时间复杂度为O(1)

3. 计算结果：

• 遍历数组中的每个数字作为A

• 计算对应的B值(B=A-C)

• 通过哈希表快速查询B的出现次数并累加

4. 输出结果：

• 打印满足条件的数对总数