思路

这题就是一个简单的a+b

a+b=c，即 b=c-a。

只需要判断第i个之前，有多少个b=c-a

就可以得出结果。

优化

暴力就是两个for循环O($N^2$)，数据范围说明我们需要优化。

下面我们将优化寻找数组里一个元素为 O(1)。

用数组记录b出现的个数，用它的索引可以实现快速寻找数组中是否存在目标元素c-a 。

使用桶的思想，可以将寻找 c-a 的时间复杂度降低到从 O(N) 降低到 O(1)。

然后for循环查找每一个目标元素，总的时间复杂度优化为O(N)

代码

#include <iostream>
using namespace std;
const int N = 1e6 + 5;
int a[N], b[N];
int st[N];
int main()
{
    int n, c;
    long long sum = 0;
    cin >> n >> c;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++)
        cin >> b[i];
    for (int i = 1; i <= n; i++)
    {
        st[b[i]]++;
        if (c > a[i])
            sum += st[c - a[i]];
    }
    cout << sum << endl;
}