二分查找的A-B问题

Question

哪位c++的OI帮我看看A-B问题，不要代码，只要思路！qwq【谢谢】

描述
同学们都还记得A+B问题吧，今天我们同样来个简单的A−B问题吧！

给出一串正整数数列以及一个正整数 C，要求计算出所有满足 A−B=C 的数对的个数（不同位置的数字一样的数对算不同的数对）。

输入描述

输入共两行。

第一行，两个正整数 N,C。

第二行，N 个正整数，作为要求处理的那串数。

输出描述

一行，表示该串正整数中包含的满足 A−B=C 的数对的个数。

用例输入 1

4 1
1 1 2 3

用例输出 1
3

谢谢

Answer 1

思路：

首先，我们可以创建一个字典（或哈希表）来存储每个数字出现的次数。

然后，我们遍历数组，对于每个数字 A，我们查找字典中是否存在 A - C ，如果存在，那么就找到了一个满足条件的数对。我们把这个数对的个数加到结果中。

注意，如果 A - C 和 A 是同一个数字，那么我们需要有至少两个这样的数字才能形成一个数对。

最后，我们返回找到的数对的个数即可。

这个算法的时间复杂度是 O(N)，因为我们只遍历数组一次。空间复杂度也是 O(N)，用于存储字典。