数列中指定差值数对的计数算法实现
在算法面试和程序设计竞赛中，处理数列中元素关系的题目非常常见。本文将针对"给定一个整数序列和差值 C，寻找满足 A - B = C 的数对个数"这一问题，探讨高效的解决方案。
问题核心与数学转化
问题的核心是统计满足特定等式的数对 $(A, B)$ 的数量。原始等式为：
A - B = C
为了方便编程实现，我们可以将其转化为：
A = B + C
这意味着对于数列中的每一个数 $B$，我们只需要寻找数列中是否存在数值等于 $B + C$ 的元素，并统计其出现的总次数。由于题目要求不同位置的相同数字需分别计算，这本质上是一个频率统计与匹配的过程。
算法思路：哈希表法
为了达到最优的时间复杂度，我们可以利用哈希表（在 C++ 中为 unordered_map）来记录数列中每个数字出现的频次。具体步骤如下：
- 遍历输入的数列，将每个数字作为键（Key），其出现的次数作为值（Value）存入哈希表。
- 再次遍历数列中的每一个数字，将其视为等式中的 $B$。
- 计算目标值 $target = B + C$。
- 在哈希表中查找 $target$ 出现的次数，并将其累加到最终结果中。
代码实现 (C++)
下面是基于上述逻辑的 C++ 代码实现，采用了 long long 类型以防止在大规模数据下统计结果溢出。
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
int main() {
// 优化标准流输入输出效率
ios::sync_with_stdio(false);
cin.tie(nullptr);
int element_count;
long long target_diff;
if (!(cin >> element_count >> target_diff)) return 0;
vector<long long> data_list(element_count);
unordered_map<long long, long long> freq_map;
// 填充数据并统计频次
for (int i = 0; i < element_count; ++i) {
cin >> data_list[i];
freq_map[data_list[i]]++;
}
long long total_pairs = 0;
// 遍历数列，寻找匹配项
for (const auto& current_val : data_list) {
long long sought_val = current_val + target_diff;
// 检查目标值是否存在于哈希表中
auto it = freq_map.find(sought_val);
if (it != freq_map.end()) {
total_pairs += it->second;
}
}
cout <lt; total_pairs <lt; endl;
return 0;
}
复杂度分析
- 时间复杂度：$O(N)$。我们对数列进行了两次线性遍历。哈希表的插入和查找操作在平均情况下的时间复杂度为 $O(1)$，因此整体效率极高，能够处理十万级甚至百万级的数据量。
- 空间复杂度：$O(N)$。空间开销主要取决于哈希表的存储以及数列本身的存储。在最坏情况下（数列中所有数字均不相同），哈希表将存储 $N$ 个键值对。
实现细节注意事项
在处理此类问题时，需要注意数据范围。如果 $C$ 或数列中的元素较大，必须使用 64 位整数（如 C++ 中的 long long）。此外，针对高频次出现的数对，最终的结果 total_pairs 也有可能超过 32 位整数的表示范围。在本题的逻辑中，使用 unordered_map 通常比 map（红黑树实现）更快，因为前者不要求维护键的有序性。
