请使用哈希表实现：题目描述 给出一串正整数数列以及一个正整数 � C，要求计算出所有满足 � − � = � A−B=C 的数对的个数（不同位置的数字一样的数对算不同的数对）。 输入 给出一串正整数数列以及一个正整数 � C，要求计算出所有满足 � − � = � A−B=C 的数对的个数（不同位置的数字一样的数对算不同的数对）。 输出 一行，表示该串正整数中包含的满足 � − � = � A−B=C 的数对的个数。请输出C++代码

#include <iostream>
#include <unordered_map>
using namespace std;

int main() {
int n, c, ans = 0;
unordered_map<int, int> map;
cin >> n >> c;

for (int i = 0; i < n; i++) {
int num;
cin >> num;
if (map[num - c]) {
ans += map[num - c];
}
map[num]++;
}

cout << ans << endl;
return 0;
}

相关问题

用c++语言写以下程序：题目描述 给出一串正整数数列以及一个正整数 C，要求计算出所有满足 A - B = C 的数对的个数（不同位置的数字一样的数对算不同的数对）。输入格式 输入共两行。 第一行，两个正整数 N,C。 第二行，N 个正整数，作为要求处理的那串数。输出格式 一行，表示该串正整数中包含的满足A−B=C 的数对的个数。

#include <iostream>
#include <unordered_map>

using namespace std;

int main() {
    int n, c;
    cin >> n >> c;
    unordered_map<int, int> m;
    int res = 0;
    for (int i = 0; i < n; i++) {
        int num;
        cin >> num;
        res += m[num - c];
        m[num]++;
    }
    cout << res << endl;
    return 0;
}

解题思路：

题目要求计算所有满足 A - B = C 的数对的个数，即 A = B + C。我们可以用哈希表来记录已经出现过的数，并且记录每个数出现的次数。对于每个数 num，我们在哈希表中查找 num - c 出现的次数，将其加到结果中，然后将 num 记录到哈希表中。这样就可以遍历整个数列，得到满足条件的数对的个数。

时间复杂度：O(n)

空间复杂度：O(n)

给出一串正整数数列以及一个正整数 C C，要求计算出所有满足 A − B = C A−B=C 的数对的个数（不同位置的数字一样的数对算不同的数对）。 输入格式 输入共两行。 第一行，两个正整数 N , C N,C。 第二行， N N 个正整数，作为要求处理的那串数。 输出格式 一行，表示该串正整数中包含的满足 A − B = C A−B=C 的数对的个数。

算法1

暴力枚举，时间复杂度 O(n^2)

算法2

哈希表，时间复杂度 O(n)

首先将所有数存入哈希表中，然后遍历数组，对于每一个数，判断其与C的差值是否在哈希表中，如果在，则说明存在一对数满足要求。

C++ 代码