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：非专业题解！有任何错误记得联系我！！！

P20004 炼气十万年 · 修为差距(二分解法)

一.解题思路

1.碎碎念

什么？！你问我为什么要在python训练题单里写cpp的题解，那当然是demon求着我出的啊嘻嘻

其实这道题是我发给他想让他做到主题单里的，但是随橙想呢家人们，他把这题塞他训练计划里了，没招了，不过我已经强烈要求他开放提交语言了，也就是说不仅限制py喽

当然，如果你仍然在练习py，那希望我这个题解能给你提供一些思路上的支持吧，至于语法就别想了，我的py也在及格线上挣扎

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

2.题目分析

这道题是想让我们去找出所有在数组中两数相减等于给定C的个数，也就是a-b=c的个数（其中a，b均属于数组num）

显然，这像是a+b Problem的变题，如果去遍历每一个数计算差值的话，很显然，复杂度会来到O(n^2)，

而这显然太暴力了！不妥！

那我们不妨换一种思路，a-b=c 不就等于 **a=b+c **吗，这样我们只需要遍历一次数组即可，找出每个数加c有几个数存在于数组内，这样就可以很优雅的得出答案了

接下来就是如何去统计有多少个数了，那么这里就要引入一个新的算法—— 二分查找 了

（PS：这题还有使用哈希表的更快解法O(n)，我会在同题的另一篇题解介绍）

我们知道，常规的查找方式，不论是直接使用count还是手写类似count查找，时间都会是n^2级别的，而如果使用二分的话，能将时间压缩到nlogn的级别

那么什么是二分呢？

二分就是每次将数组分成两部分，然后保留需要的那一部分，再重复此操作直到找到答案

二分查找的前提是 数组有序 🌰 给你一个数组num= [1,2,2,3] 当我们要找某个目标值（比如 2）在数组里出现了几次时，就可以用二分查找快速定位：

1.找到 第一个等于 2 的位置（比如下标 1）

2.找到 第一个大于 2 的位置（比如下标 3）

3.出现次数 = 下标3 - 下标1 = 2

在cpp98及以后的所有版本，都支持使用二分的迭代器lower_bound 和 upper_bound

不过我还是建议你去学一下手打二分，这对你学习算法的思维或许会有帮助！

3.算法实现

1.排序：对 num 进行升序排序

2.遍历每个数 b：

• 计算目标值 target = b + C
• 在排序后的数组中，用二分查找找到 target 出现的第一个位置（lower_bound）和最后一个位置的后一个（upper_bound）
• 目标值的出现次数 = upper_bound - lower_bound
• 累加到答案中

3.输出答案（注意用 long long 防止溢出）

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

4.复杂度

时间：O(n log 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);
    for(int i = 0;i<n;++i){
        cin>>num[i];
    }

    int ans = 0;
    sort(num.begin(),num.end());
    
    for(auto x:num){
        int a = x + c;
        auto l = lower_bound(num.begin(),num.end(),a);
        auto r = upper_bound(num.begin(),num.end(),a);
        if(c==0){
            ans += r-l-1;
        }else{
            ans += r-l;
        }
        
    }
    cout<<ans<<'\n';

    return 0;
}

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