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

五、总结

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

来源:洛谷题解

评论

暂无评论