找回密码
 立即注册
查看: 19|回复: 0

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

[复制链接]
  • 打卡等级:即来则安
  • 打卡总天数:17
  • 打卡月天数:1
  • 打卡总奖励:185
  • 最近打卡:2025-08-06 09:29:10

21

主题

8

回帖

1万

积分

VIP

积分
10208
发表于 2025-7-20 11:35:08 | 显示全部楼层 |阅读模式
截图未命名.jpg
一、题目解读
洛谷P1102题要求处理一组整数数组与常数C,统计数组中是否存在元素A与B满足A+B=C。用户需输出满足条件的数对数量。题目关键在于快速判断是否存在互补元素,时间复杂度需优化以避免暴力遍历。
二、解题思路
采用哈希表(unordered_map)实现高效统计。首先遍历数组,记录每个元素的出现次数;再遍历数组计算每个元素的“目标值”(即C-当前元素),通过哈希表直接查询目标值是否存在及其频率,从而快速累加有效数对。此思路将时间复杂度从O(n²)降至O(n),利用空间换时间策略。
三、解题步骤
1. 输入数组长度n与常数C,初始化哈希表countMap。
2. 遍历数组,记录每个元素nums的出现次数至countMap。
3. 第二次遍历数组,对每个nums计算目标值target = nums + C。
4. 若target存在于countMap中,累加其次数至结果res(注意:若A=B需避免重复计数)。
5. 输出最终数对数量res。
四、代码与注释
  1. #include <iostream>
  2. #include <unordered_map>
  3. #include <algorithm>
  4. using namespace std;

  5. const int MAXN = 2e5 + 5; // 定义**数组长度
  6. long long nums[MAXN];

  7. int main() {
  8. int n; // 数组长度
  9. long long c; // 常数C
  10. cin >> n >> c;

  11. unordered_map<long long, int> countMap; // 哈希表,记录元素频次
  12. for(int i = 0; i < n; i++) {
  13. cin >> nums[i];
  14. countMap[nums[i]]++; // 统计每个数字出现次数
  15. }

  16. long long res = 0; // 结果计数器
  17. for(int i = 0; i < n; i++) {
  18. long long target = nums[i] + c; // 计算需要的B值(A+B=C)
  19. res += countMap[target]; // 累加满足条件的数对数量
  20. }

  21. cout << res << endl;
  22. return 0;
  23. }
复制代码


五、总结
该解法巧妙利用哈希表的快速查询特性,将数对统计转化为单次遍历与频次累加。核心在于预处理元素频率,避免重复计算。适用于数据量大但元素范围有限的场景,为同类问题提供高效模板。注意实际应用中需评估哈希表空间开销与冲突风险。
来源:洛谷题解
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

SEO网站 ( 冀ICP备2025113422号-2 )|网站地图

Powered by Discuz! X3.5

快速回复 返回顶部 返回列表