A-B 数对

题目描述

出题是一件痛苦的事情!

相同的题目看多了也会有审美疲劳,于是我舍弃了大家所熟悉的 A+B Problem,改用 A-B 了哈哈!

好吧,题目是这样的:给出一串数以及一个数字 C,要求计算出所有A−B=C 的数对的个数(不同位置的数字一样的数对算不同的数对)。
输入格式

输入共两行。

第一行,两个整数 N,C。

第二行,N 个整数,作为要求处理的那串数。
输出格式

一行,表示该串数中包含的满足 A−B=C 的数对的个数。
输入输出样例
输入 #1

4 1
1 1 2 3

输出 #1

3

说明/提示

对于 75% 的数据,1≤N≤2000。

对于 100% 的数据1≤N≤2×105

保证所有输入数据都在 32 位带符号整数范围内。

2017/4/29 新添数据两组

题目分析+解题思路

O(n2)思路

就是将A−B=C变成A=B+C,朴素的算法是一个二重循环,当然我们知道这肯定会超时的。

O(nlogn)思路

利用二分,一遍循环枚举找BBB,中间二分找C,时间复杂度O(nlogn),可以通过本题

也可以利用stlstlstl中自带的红黑树map达到AC的效果

O(n)思路

优化一点的算法呢则是用桶去保存每个数,这样我们就只需要枚举B,然后判断一下C存不存在就行了,这样的时间复杂度是O(n),当然此算法空间复杂度很高会MLE
正题

好吧,前面讲了这么多都是为了告诉你各算法的优缺点,自然在目前来看,HASHHASHHASH解法是最优秀的(除了打表),那么具体怎样实现呢?

实现

前面讲O(n)算法的时候,讲过用桶去做,这样的代价是用空间换时间,需要的空间代价是极高的,而HASH就是避免了这一点。

其实我们可以发现,桶数组中是有很多桶是没有用到的,也就是浪费了空间,比如有4个数

2 4 7 10001

用桶你就必须得开一个10001的数组,而用HASH只需要开一个长度为4的数组,它们的位置分别为

2%4=2 4%4=0 7%4=3 10001%4=1

在HASH表中表示为

0 1 2 3

4 10001 2 7

明白了吗?其实就是%一个数而已,若%的过程中,这个位置已经有数了,那么就放在它的后面就行了,以此类推。

需要注意的是统计数量,本人的处理方法使用结构体保存数量(即出现相同解的时候)

AC代码

#include<iostream>
#include<cstdio>
using namespace std;
const long long M=1000007;
long long s,x[M];
struct node
{
   
	long long sum,num;
}a[M];
long long h(long long x1)
{
   
	return x1%M;
}
long long dw(long long x)//定位
{
   
	long long i=0,o=h(x);
	while(a[(i+o)%M].sum!=0&&a[(i+o)%M].sum!=x&&i<M)
	 i++;
	return (i+o)%M;
}
int main()
{
   
	int n,c;
	scanf("%d%d",&n,&c);
	for(int i=1;i<=n;i++)
	{
   
		scanf("%d",&x[i]);
		int l=dw(x[i]);
		if(a[l].sum==x[i])a[l].num++;//出现次数
		else a[l].num=1;
		a[l].sum=x[i];//赋值
	}
	for(int i=1;i<=n;i++)
	 s+=a[dw(x[i]-c)].num;//累加
	cout<<s;
}

谢谢