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

19339201706

一、问题描述

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

二、算法核心思想

• 哈希表统计：使用unordered_map统计每个数字出现的次数
• 线性扫描：遍历数组，对每个元素A，查找满足B=A-C的元素B的数量
• 累加结果：将所有满足条件的B的数量累加得到最终结果
  
  

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

1. #include <iostream>
   
2. #include <unordered_map>
   
3. #include <algorithm>
   
4. using namespace std;
   
5. 
   
6. const int MAXN = 2e5 + 5;  // 定义最大数组大小
   
7. long long nums[MAXN];      // 存储输入数字的数组
   
8. 
   
9. int main() {
   
10.     int n;                 // 数字个数
    
11.     long long c;           // 目标差值C
    
12.     cin >> n >> c;         // 输入n和c
    
13.    
    
14.     // 使用哈希表统计每个数字出现的次数
    
15.     unordered_map<long long, int> countMap;
    
16.     for(int i = 0; i < n; i++) {
    
17.         cin >> nums[i];            // 读取数字
    
18.         countMap[nums[i]]++;       // 统计该数字出现次数
    
19.     }
    
20.    
    
21.     long long res = 0;             // 初始化结果计数器
    
22.     for(int i = 0; i < n; i++) {
    
23.         long long target = nums[i] + c;  // 计算需要的B值(A-B=C => B=A-C)
    
24.         res += countMap[target];         // 累加满足条件的B的数量
    
25.     }
    
26.    
    
27.     cout << res << endl;           // 输出结果
    
28.     return 0;
    
29. }

复制代码

四、算法分步解析

• 输入处理：
  
  
  • 读取数字个数n和目标差值c
  • 定义足够大的数组存储输入数字
    
    
• 统计频率：
  
  
  • 使用unordered_map统计每个数字出现的次数
  • 哈希表的平均插入和查询时间复杂度为O(1)
    
    
• 计算结果：
  
  
  • 遍历数组中的每个数字作为A
  • 计算对应的B值(B=A-C)
  • 通过哈希表快速查询B的出现次数并累加
    
    
• 输出结果：
  
  
  • 打印满足条件的数对总数
    
    

来源：洛谷题解