可是我真的会伤心

题目链接

思路：1.本来想的是暴力，两层循环模拟每个数。

2.后来想先把每个数字的个数求出来放在数组nums【】中，并把不重复的数字存到数组b，再两层循环b数组应该时间复杂度会好些，如果b数组中的两个数满足条件，则把nums【i】*nums【b】加入到答案ans中。

暴力代码：76分

#include<algorithm>
#include<iostream>
#include<cstring>
#include<queue>
#include<cmath>

using namespace std;

int n,c;
long long a[1000010];
int cnt;

int main()
{
	scanf("%d%d",&n,&c);
	for(int i=0;i<n;i++){
		scanf("%lld",&a[i]);
	}
	sort(a,a+n);
	//先思考暴力的
	//可以用窗口 
	for(int i=0;i<n-1;i++){
		for(int j=i+1;j<n;j++){
			if(a[j] - a[i] == c){
				cnt++;
			}
		}
	} 
	printf("%d",cnt);
	return 0;
}

结果：

尝试代码：

#include<algorithm>
#include<iostream>
#include<cstring>
#include<queue>
#include<cmath>

using namespace std;

int n,c;
long long a[1000010];
long long b[1000010];

int nums[1000010]; 
int cnt;
int t;

int main()
{
	scanf("%d%d",&n,&c);
	for(int i=0;i<n;i++){
		scanf("%lld",&a[i]);
	}
	sort(a,a+n);
	nums[a[0]] = 1;
	b[0] = a[0];
	//找出每个数对应的个数，如果它减取前面一个数等于c就直接加上他的个数
	for(int i=1;i<n;i++){
		if(a[i] != a[i-1]){
			t++;
			nums[a[i]] ++;
			b[t] = a[i];
		}
		else nums[a[i]] ++;
	}
//	for(int i=0;i<=t;i++){
//		cout<<b[i]<<" ";
//	}
//	cout<<endl;
	
//	for(int i=0;i<100;i++){
//		cout<<nums[i]<<" ";
//	}
//	cout<<endl;
	for(int i=0;i<t;i++){
		for(int j=i+1;j<=t;j++){
			if(b[j] - b[i] == c){
				cnt += nums[b[j]] * nums[b[i]];
			}
		}
	}
	printf("%d",cnt);
	return 0;
 } 

结果：

代码3：不开龙永远的痛

#include<algorithm>
#include<iostream>
#include<cstring>
#include<queue>
#include<cmath>

using namespace std;

long long n,c;
long long a[1000010];
long long b[1000010];

long long nums[1000010]; 
long long cnt;
long long t;

int main()
{
	scanf("%lld%lld",&n,&c);
	for(int i=0;i<n;i++){
		scanf("%lld",&a[i]);
	}
	sort(a,a+n);
	nums[a[0]] = 1;
	b[0] = a[0];
	//找出每个数对应的个数，如果它减取前面一个数等于c就直接加上他的个数
	for(int i=1;i<n;i++){
		if(a[i] != a[i-1]){
			t++;
			nums[a[i]] ++;
			b[t] = a[i];
		}
		else nums[a[i]] ++;
	}
//	for(int i=0;i<=t;i++){
//		cout<<b[i]<<" ";
//	}
//	cout<<endl;
	
//	for(int i=0;i<100;i++){
//		cout<<nums[i]<<" ";
//	}
//	cout<<endl;
	for(int i=0;i<t;i++){
		for(int j=i+1;j<=t;j++){
			if(b[j] - b[i] == c){
				cnt += nums[b[j]] * nums[b[i]];
			}
		}
	}
	printf("%lld",cnt);
	return 0;
 } 

结果：92分

AC代码：用map

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<bits/stdc++.h>
using namespace std;
int n,c;
int a[200010];
long long ans;
map<int, int> m;//map是映射,map<A,B> 字母A对应个数B 
int main()
{
	scanf("%d%d",&n,&c);
	for(int i = 1; i <= n; i++){
		scanf("%d",&a[i]);
		m[a[i]] ++;
	}
	for(int i = 1; i <= n; i++){
		ans += m[a[i] + c];
	}
	printf("%lld",ans);
	return 0;
}