大学保研机试-2022-差分计数

会员或题库专享

请先，开通会员或购买题库保研机考题库，可解锁完整内容。

购买保研机考题库开通会员

会员专享

请先登录，登录后可使用今日免费解锁；开通会员，或购买该题目所属题库（保研机考题库），可解锁完整内容。

购买题库开通会员

思路

1.双指针暴力法

双重循环枚举 $i,j$ 来计数即可,复杂度是 $O(n^2)$ 。但是无法拿到满分。服务器一般一秒跑 $1e8$ 次。

把 $n$ 带进去看看 $(2 * 10^6)^2=4 * 10^{12} >> 1e8$

给定 $n$ 个整数 $a_1,...,a_n$ 和一个整数 $x$ 。求有多少不同下标对 $(i,j$ )满足 $a_i-a_j= x$ 。 (1, 5) 和 (5, 1) 不一样，但(1, 1) 和 (1, 1) 一样。