题目描述

给出一串正整数数列以及一个正整数 $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}$。

算法1

(双指针) $O(nlog_2n)$

将原数组排序，相同大小的数排在一起，若该数字可以与其他数构成数对，则于其大小相同的数也可以，可以用两个指针$j,k$维护相同数字的区间，每当$i,j$构成数对时，$ans+=k-j$。

时间复杂度

指针$i$作为主指针遍历整个数组，时间复杂度为$O(n)$，但排序的时间复杂度为$O(nlog_2n)$，总时间复杂度为$O(nlog_2n)$。

参考文献

《算法竞赛》

Python 代码

优化代码

n,c=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
j=0
k=0
cnt=0
for i in range(1,n):
    while j<i and a[i]-a[j]>c:
        j+=1
    while k<i and a[i]-a[k]>=c:
        k+=1
    if a[i]-a[j]==c:
        cnt+=k-j
print(cnt)

《算竞》代码

n,c=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
j=0
k=0
ans=0
for i in range(n):
    while j<n-1 and a[i]-a[j]>c:
        j+=1
    while k<n and a[i]-a[k]>=c:
        k+=1
    if j<n and k<=n and a[i]-a[j]==c and a[i]-a[k-1]==c:
        ans+=k-j
print(ans)

算法2

(二分) $O(nlog_2n)$

先排序；枚举$b$,二分查找$a$第一次出现的下标和最后一次出现(的后面)的下标，得到$a$的个数，得到$a,b$数对的个数。

时间复杂度

排序$O(nlog_2n)$，n次$(O(n))$二分查找$(O(log_2n))$，总时间复杂度$O(nlog_2n)$

参考文献

《深基》

Python 代码

from bisect import bisect_left,bisect
n,c=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
cnt=0
for i in range(n):
    x=a[i]+c
    cnt+=bisect(a,x)-bisect_left(a,x)
print(cnt)