考虑到, $ 1 \le N \le 2 \times 10^5 $, $ O(n^2) $ 的暴力判断无法通过此题, 下面给出三种可行的解决方案。
1.哈希
容易想到的一个思路是：用哈希表记录一下 $ a_1 \sim a_n $ 每个数出现了多少次, 然后求出 $ \Sigma_{i = 1}^n cnt_{a_i - c} $ 即可, $ cnt_{a_i} $ 表示 $ a_i $ 在序列中出现的次数。需要注意的是, $ a_i < 2^{30} $, 数组无法开辟如此大的空间, 需要用 std::map 处理, 时间复杂度为 $ O(nlog_2n) $。
点击查看代码
#include <bits/stdc++.h>
#define lint long long
using namespace std;
int main() {
map<int, int> cnt;
int n, c;
scanf("%d%d", &n, &c);
vector<int> a(n + 1);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
cnt[a[i]]++;
}
lint ans = 0;
for (int i = 1; i <= n; i++) {
ans += cnt[a[i] - c];
}
printf("%lld\n", ans);
return 0;
}