C++ 计算数对个数：a-b=c

C++ 计算数对个数：a-b=c

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

输入

共两行。第一行两个整数 'n', 'c'。

第二行 'a1,a2,a4...' 个整数，作为要处理的那串数。

输出

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

样例输入

6 3
8 4 5 7 7 4

样例输出

5

C++ 代码

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

using namespace std;

int main() {
    int n, c;
    cin >> n >> c;
    vector<int> nums(n);
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }
    
    unordered_map<int, int> count;
    int ans = 0;
    for (int i = 0; i < n; i++) {
        int a = nums[i];
        int b = a - c;
        if (count.find(b) != count.end()) {
            ans += count[b];
        }
        count[a]++;
    }
    
    cout << ans << endl;
    
    return 0;
}

算法解释

1. 使用 unordered_map 存储每个数字出现的次数。
2. 遍历数组，对于每个数字 'a'，计算 'b = a - c'。
3. 如果 'b' 在 unordered_map 中存在，则说明存在一对数字满足 'a-b=c'，计数器 'ans' 加上 'b' 的出现次数。
4. 遍历结束后，'ans' 就是满足条件的数对个数。

代码解析

• unordered_map<int, int> count;：定义一个 unordered_map 来存储每个数字出现的次数。
• ans += count[b];：如果 'b' 在 unordered_map 中存在，则说明存在一对数字满足 'a-b=c'，计数器 'ans' 加上 'b' 的出现次数。
• count[a]++;：将 'a' 的出现次数加 1。

优化建议

• 使用 unordered_set 替代 unordered_map 可以提高效率，因为我们只需要判断数字是否存在，不需要记录出现次数。
• 可以在输入时直接将数字存入 unordered_set，避免了额外的遍历步骤。
• 可以考虑使用更优化的算法，例如使用哈希表或双指针技术。