P20004 炼气十万年 · 修为差距(哈希表解法)

一.解题思路

1.碎碎念

今天静静听社长唠叨了一堆，学算法的话就好好学啦大家，还是不要有太多的小心思的好，人与人间的关系好复杂，还是当一个纯粹点的技术佬吧😇

推荐大家听听反乌托邦，豪庭！

反乌托邦 ：https://www.bilibili.com/video/BV1CVPoeNEq4?vd_source=b4434b4fd9de4d42afcaa6c0de7907cf

反乌托邦Pt.2：https://www.bilibili.com/video/BV1nV6ZBcEyH?vd_source=b4434b4fd9de4d42afcaa6c0de7907cf

（如果看完对你有帮助记得点个赞再走呗嘻嘻嘻✨）

2.题目分析

上一讲已经带大家过了思路了，所以这里不做介绍，具体看同题的另一篇题解P20004 炼气十万年 · 修为差距(二分解法)

那么好，我们现在来讲一下什么是哈希表

哈希表是一种 键-值对 数据结构，它内部有一个数组，通过 哈希函数 ，把“键”算成一个数字索引，然后把“值”存到数组的这个位置，查找时，用同样的哈希函数算出索引，就能直接去那个位置取数据，所以理论上哈希表的查询速度可以来到极快的O(1)

而在本题中，我们可以将num中的数存成key，将出现次数存成value，这样我们只需要查询b+c所对应的value就好了

cpp中哈希表为unordered_map<int,int>

3.算法实现

1.建立哈希表：unordered_map<int,int> cnt;

2.查询：for(auto b:num){ans+=cnt[b+c];}

3.输出结果（注意用 long long 防止溢出）

注意：如果题目中C为正整数，那么这题就到这就结束了，但是可恶的demon明明题目写的C为正整数，测试集却给你C = 0的数据（题解发布时尚未整改），所以需要考虑C=0的情况，而如果c等于0的话，a=b+c就会变成a=b，这会错误的将b自身统计进去一次，所以需要每次都-1保证答案正确（这种情况其实就变成了找num中有几个除了自己以外相同的数了）

4.复杂度

时间：O(n)

空间：O(n)

二.完整代码

#include <bits/stdc++.h>
using namespace std;
#define int long long

signed main(){

    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n,c;
    cin>>n>>c;
    vector<int> num(n);
    unordered_map<int, int> cnt;
    
    for (int i = 0;i<n;++i) {
        cin>>num[i];
        cnt[num[i]]++;
    }
    
    int ans = 0;
    for (int b:num) {
        ans += cnt[b + c];
        if(c==0)
            ans--;
    }
    
    cout<<ans<<'\n';
    return 0;
}

PS：非专业题解！有任何错误记得联系我！！！