一、题目解读洛谷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。 四、代码与注释
- #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;
- }
五、总结该解法巧妙利用哈希表的快速查询特性，将数对统计转化为单次遍历与频次累加。核心在于预处理元素频率，避免重复计算。适用于数据量大但元素范围有限的场景，为同类问题提供高效模板。注意实际应用中需评估哈希表空间开销与冲突风险。
| 
发表于 2025-7-20 11:34:47
