P1102 A-B 数对

题目链接：

一开始的想法：排序后枚举，但这样显然是 \(O(n^2)\) 的复杂度，会超时

#include <cstdio>
#include <algorithm>

const int N = 2e5 + 5;

int a[N];

int main()
{
    int n, c, res = 0;
    scanf("%d%d", &n, &c);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    std::sort(a, a + n);
    for (int i = 0; i < n - 1; i++) {
        for (int j = i + 1; j < n; j++) {
            if (a[j] - a[i] == c) res++;
        }
    }
    printf("%d", res);
    return 0;
}

优化方式一： \(\rm map映射\) \(O(n)\)

将 \(A-B=C\) 变形为 \(A-C=B\)。用 \(\rm map\) 记录数组中每个元素的出现次数然后将每个元素都减去 \(c\)，最后再遍历一遍数组求出当前所有元素分别在 \(\rm map\) 中的次数之和（即这些元素在原数组中的出现次数）。由于最坏情况可能达到 \(10^{10}\) 会爆 \(\rm int，\)因此要用 \(\rm long\) \(\rm long\)

#include <bits/stdc++.h>

using namespace std;
using LL = long long;

const int N = 2e5 + 5;

int a[N];
map<int, int> p;

int main()
{
    int n, c;
    LL res = 0;
    scanf("%d%d", &n, &c);
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
        p[a[i]]++;
        a[i] -= c;
    }
    for (int i = 0; i < n; i++) 
        res += p[a[i]];
    printf("%lld", res);
    return 0;
}