02Bucket思想：A-B 数对

好题记录2023.9-1

题目：

A-B 数对

题目背景

出题是一件痛苦的事情！

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

题目描述

给出一串正整数数列以及一个正整数 $C$，要求计算出所有满足 $A - B = C$ 的数对的个数（不同位置的数字一样的数对算不同的数对）。

输入格式

输入共两行。

第一行，两个正整数 $N,C$。

第二行，$N$ 个正整数，作为要求处理的那串数。

输出格式

一行，表示该串正整数中包含的满足 $A - B = C$ 的数对的个数。

样例 #1

样例输入 #1

4 1
1 1 2 3

样例输出 #1

3

提示

对于 $75\%$ 的数据，$1 \leq N \leq 2000$。

对于 $100\%$ 的数据，$1 \leq N \leq 2 \times 10^5$，$0 \leq a_i <2^{30}$，$1 \leq C < 2^{30}$。

2017/4/29 新添数据两组

思路

O(n2)思路

楼下的题解讲的很清楚，就是将A−B=C变成A=B+C，朴素的算法是一个二重循环，当然我们知道这肯定会超时的。

O(nlogn)思路（笔者采用这个思路）

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

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

O(n)思路

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

#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<algorithm>
using namespace std;
int binary_search_low(long long a[],long long key,long long low,long long high)
{
    long long i=low,mid;
    long long j=high,flag=-1;
    while(i<=j)
    {
        mid=(i+j)/2;
        if(a[mid]>=key)
        {
            j=mid-1;
        }
        else
        {
            i=mid+1;
        }
    }
    if(a[i]==key)
    {
        flag=i;
    }
    return flag;
}
int binary_search_high(long long a[],long long key,long long low,long long high)
{
    long long i=low,mid;
    long long j=high,flag=-1;
    while(i<=j)
    {
        mid=(i+j)/2;
        if(a[mid]>key)
        {
            j=mid-1;
        }
        else
        {
            i=mid+1;
        }
    }
    if(a[j]==key)
    {
        flag=j;
    }
    return flag;
}
int main(void){
    long long i,j,n,c,mid,flag1,ans=0,flag2;
    cin>>n>>c;
    long long a[n],key;

    for (int i=0;i<n;i++)
    {
        cin>>a[i];
    }

    sort(a,a+n);

    for (int i=0;i<n;i++)
    {
        flag1=binary_search_high(a,a[i]+c,i+1,n-1);
        flag2=binary_search_low(a,a[i]+c,i+1,n-1);
        if(flag1!=-1 && flag2!=-1)
        {
            ans+=(flag1-flag2+1);
        }
    }
    cout<<ans<<endl;
    return 0;
}

当然sort部分可以编写快速排序，但是不给过，有两个测试点超时

以下内容看不懂

正题

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

实现

前面讲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

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