洛谷P1102题解：利用哈希表优化的数对统计 C++代码解析

一、题目解读

洛谷P1102题要求处理一组整数数组与常数C，统计数组中是否存在元素A与B满足A+B=C。用户需输出满足条件的数对数量。题目关键在于快速判断是否存在互补元素，时间复杂度需优化以避免暴力遍历。

二、解题思路

采用哈希表（unordered_map）实现高效统计。首先遍历数组，记录每个元素的出现次数；再遍历数组计算每个元素的“目标值”（即C-当前元素），通过哈希表直接查询目标值是否存在及其频率，从而快速累加有效数对。此思路将时间复杂度从O(n²)降至O(n)，利用空间换时间策略。

三、解题步骤

1. 输入数组长度n与常数C，初始化哈希表countMap。

2. 遍历数组，记录每个元素nums[i]的出现次数至countMap。

3. 第二次遍历数组，对每个nums[i]计算目标值target = nums[i] + C。

4. 若target存在于countMap中，累加其次数至结果res（注意：若A=B需避免重复计数）。

5. 输出最终数对数量res。

四、代码与注释

#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;
    
    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）
        res += countMap[target];  // 累加满足条件的数对数量
    }
    
    cout << res << endl;
    return 0;
}

五、总结

该解法巧妙利用哈希表的快速查询特性，将数对统计转化为单次遍历与频次累加。核心在于预处理元素频率，避免重复计算。适用于数据量大但元素范围有限的场景，为同类问题提供高效模板。注意实际应用中需评估哈希表空间开销与冲突风险。