C++ 算法：计算数组中满足 a-b=c 的数对个数

C++ 算法：计算数组中满足 a-b=c 的数对个数

问题描述：

给出一串数以及一个数字 c，要求计算出所有 a-b=c 的数对的个数（不同位置得到数字一样的数对算不同的数对）。

输入：

共两行。第一行两个整数 n,c。 第二行 n个整数a1,a2,a3,...an(|ai|<=1e9)，作为要处理的那串数。

输出：

该数串中包含的满足a-b=c的数对的个数

样例输入：

6 3
8 4 5 7 7 4

样例输出：

5

C++ 代码实现：

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

int countPairs(vector<int>& nums, int c) {
    int count = 0;
    unordered_map<int, int> mp;
    for (int num : nums) {
        mp[num]++;
        count += mp[num - c];
    }
    return count;
}

int main() {
    int n, c;
    cin >> n >> c;
    vector<int> nums(n);
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }
    int result = countPairs(nums, c);
    cout << result << endl;
    return 0;
}

算法解释：

1. 使用 unordered_map 存储数组中每个数字出现的次数。
2. 遍历数组，对于每个数字 num，在哈希表中查找是否存在 num - c 的数字。
3. 如果存在，则说明找到了一个满足条件的数对，计数器 count 加 1。
4. 最后返回 count 的值，即满足 a-b=c 的数对的个数。

代码说明：

• countPairs(vector<int>& nums, int c) 函数用于计算满足条件的数对个数。
• mp 是一个哈希表，用于存储数组中每个数字出现的次数。
• count 是计数器，用于记录满足条件的数对的个数。
• main() 函数用于输入数据，调用 countPairs() 函数计算结果，并输出结果。

总结：

本文介绍了使用 C++ 语言实现计算数组中满足 a-b=c 的数对个数的算法，并提供了详细的代码示例和解释。该算法利用哈希表来高效地统计数组中每个数字出现的次数，从而快速找到满足条件的数对。