题意

求序列里面有多少个$A-B=C$

$C$为输入的数字

思路

map用于存储每一个数字出现的次数

• 注意,不可以用数组计数代替map

求序列里面有多少个$A-B=C$

只要反推

枚举$B$,查找$A$是否存在,然后统计符合的个数

代码

时间复杂度$O(n log_2n)$

不开 long long 见祖宗

#include<iostream>
#include<map>
#define int long long
using namespace std;
map<int,int>m;//数字,出现的个数
int n,c,sum=0;
signed main()
{
    cin>>n>>c;//输入
    for(int i=0;i<n;i++)
    {
        int s;
        cin>>s;//输入
        m[s]++;//增加次数
    }
    for(auto i:m)//c++11迭代
    {
        int s=c+i.first;//求A
        if(m.find(s)!=m.end())//寻找A是否存在,等于二分查找
        {
            sum+=i.second*m[s];//添加个数,求对数,就是相乘
        }
    }
    cout<<sum;//输出
    return 0;//完结散花
}

我们看到m.find这里,老师讲过,find可以查找是否存在某元素

但是,map也可以通过索引查找元素,如果值为0说明不存在(当然,可能值就是0,只是这道题可以适用)

但是如果有留意,你会发现这样查找,找完后会有添加新的键值对

所以还要删掉这个键值对

这样就可以优化了

时间复杂度看似是$O(n)$

但是通过这个CSDN博客可以看到,map的基操基本都是$O(log_2n)$,所以正解的时间复杂度还是$O(n log_2n)$

这算是另一种解法

不开 long long 见祖宗

#include<iostream>
#include<map>
#define int long long
using namespace std;
map<int,int>m;//数字,出现的个数
int n,c,sum=0;
signed main()
{
    cin>>n>>c;//输入
    for(int i=0;i<n;i++)
    {
        int s;
        cin>>s;//输入
        m[s]++;//增加次数
    }
    for(auto i:m)//c++11迭代
    {
        int s=c+i.first;//求A
        sum+=i.second*m[s];//添加个数,求对数,就是相乘
        if(m[s]==0)//如果不存在A
			m.erase(s);//记得删掉,不然MLE
    }
    cout<<sum;//输出
    return 0;//完结散花
}