【二分4】塔子哥的数对问题
题解
题面分析
给定一个长度为 n 的整数数组 A 和一个整数 C,需要计算所有满足条件 A[i]−A[j]=C 的数对 (i,j) 的个数,其中 i 和 j 为数组中不同的位置索引。需要注意的是,如果数组中存在重复的元素,即使数值相同但位置不同,也应视为不同的数对。
思路
题目描述:
给定一个整数数组A和一个整数C,要求计算出所有满足A[i]−A[j]=C的数对 (i,j)的个数,其中i和j为数组中的不同位置索引。注意,若A[i]和A[j]的值相同,但位置不同,则算作不同的数对。
输入:
- 第一行输入一个整数 n(1≤n≤105),表示数组 A 的大小。
- 第二行输入 n 个整数,表示数组 A 的元素 A[1],A[2],…,A[n](1≤A[i]≤109)。
- 第三行输入一个整数 C(1≤C≤109)。
输出:
输出一个整数,表示满足条件的数对 (i,j) 的个数。
样例输入:
6
1 2 2 3 4 5
2
样例输出:
4
说明:
在上述样例中,满足 A[i]−A[j]=2 的数对为:
- (1,4) 对应 (3−1=2)
- (2,5) 对应 (4−2=2)
- (3,5) 对应 (4−2=2)
- (4,6) 对应 (5−3=2)
因此,总数对个数为 4。