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