题意

求序列里面有多少个$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;//完结散花
}

题意

数组里有多少个「A-B 数对」

A-B 数对：数对满足 $A-B=C$

思路

学过穿衣服配对吧，就是 3 件衣服 2 件裤子求有多少种组合。这里也是一样。记录每个数出现的次数，然后遍历每个数。$i$ 为 $A$，$i - C$ 得到 $B$，然后总数加上 $a_A \times a_B$

不开 long long 见祖宗

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
map<int,int> a;
int cnt;
signed main(int argc, char **argv){
	int n,c;
	cin >> n >> c;
	for (int i = 0;i < n;i++){
		int x;
		cin >> x;
		a[x]++;
	}
	for (auto i : a)	cnt += a[i.first - c] * i.second;
	cout << cnt;
	return 0;
}

参考与鸣谢

从 @ 的代码中获得了思路