哈希表方案思考

核心转换

• 问题：找满足 A - B = C 的数对
• 转换为：A = B + C
• 对于每个 B，我们需要查找是否存在 B + C

算法步骤

第一步：建立频率哈希表

扫描一遍数列，用 map 或 unordered_map 记录每个数字出现的频率：

• key：数字本身
• value：出现次数

第二步：遍历每个数字B，查找对应的A

对数列中的每个数字 B（作为减数）：

• 计算 A = B + C（被减数）
• 在哈希表中查询 A 是否存在
• 如果存在，加上 A 的频率到答案中

简单示例演算

数列：1 1 2 3，C = 1

第一步：建立哈希表

{1: 2, 2: 1, 3: 1}

第二步：遍历查找

- B=1(第1个): 需要A=2，哈希表中2出现1次 → 答案 += 1
- B=1(第2个): 需要A=2，哈希表中2出现1次 → 答案 += 1
- B=2(第3个): 需要A=3，哈希表中3出现1次 → 答案 += 1
- B=3(第4个): 需要A=4，哈希表中无4 → 答案 += 0

答案 = 1 + 1 + 1 + 0 = 3 ✓

---

复杂例子：数字重复且位置混乱

数列：1 1 2 3 2 4，C = 1

第一步：建立哈希表

{
  1: 2,    // 1出现2次
  2: 2,    // 2出现2次
  3: 1,    // 3出现1次
  4: 1     // 4出现1次
}

第二步：遍历每个B，查找对应的A

对每个B的出现位置进行遍历：

B=1(位置1): 需要A=2，哈希表中2出现2次 → 答案 += 2
           (配对：(2[位置3], 1[位置1]) 和 (2[位置5], 1[位置1]))

B=1(位置2): 需要A=2，哈希表中2出现2次 → 答案 += 2
           (配对：(2[位置3], 1[位置2]) 和 (2[位置5], 1[位置2]))

B=2(位置3): 需要A=3，哈希表中3出现1次 → 答案 += 1
           (配对：(3[位置4], 2[位置3]))

B=3(位置4): 需要A=4，哈希表中4出现1次 → 答案 += 1
           (配对：(4[位置6], 3[位置4]))

B=2(位置5): 需要A=3，哈希表中3出现1次 → 答案 += 1
           (配对：(3[位置4], 2[位置5]))

B=4(位置6): 需要A=5，哈希表中无5 → 答案 += 0

答案 = 2 + 2 + 1 + 1 + 1 + 0 = 7

为什么这样想？

数对的定义

"不同位置的数字一样的数对算不同的数对"意味着：

• (A的位置, B的位置) 是数对的唯一标识
• 位置在前还是在后完全不影响

频率的作用

• 当 B 出现多次时，每个 B 都能和所有符合条件的 A 配对
• 当 A 出现多次时，每个 B 都能和每个 A 配对
• 结果自动累加：B的频率 × A的频率

简化理解

不遍历每个位置，直接用频率计算：

答案 = ∑(每种不同的B值) [B值在哈希表中的频率 × 对应A值在哈希表中的频率]

对于 1 1 2 3 2 4, C=1:
- B值为1时：A值为2，B频率=2，A频率=2，贡献 2×2 = 4
- B值为2时：A值为3，B频率=2，A频率=1，贡献 2×1 = 2
- B值为3时：A值为4，B频率=1，A频率=1，贡献 1×1 = 1
- B值为4时：A值为5，B频率=1，A频率=0，贡献 1×0 = 0

总答案 = 4 + 2 + 1 + 0 = 7 ✓

---

核心要点

✓ 哈希表自动处理了重复和位置问题——通过频率计数，每一对 (值A, 值B) 的组合都被准确地计数了！

✓ 时间复杂度： O(N log N)（使用 map，查找为 log N）或 O(N)（使用 unordered_map）

✓ 空间复杂度： O(N)

✓ 实现细节： 用 long long 作为key，因为 aᵢ < 2³⁰，相加可能超过 int 范围

---

时间复杂度详细分析

使用 map<long long, long long> 的情况

第一步：建立频率哈希表

for (int i = 0; i < n; i++) {
    cin >> arr[i];
    freq[arr[i]]++;
}

• 读入 n 个数字：O(n)
• 每次 freq[arr[i]]++ 操作：O(log n)（map 的插入/查找）
• 第一步总时间：O(n log n)

第二步：遍历查找并累加

for (int i = 0; i < n; i++) {
    long long b = arr[i];
    long long a = b + c;
    if (freq.find(a) != freq.end()) {
        ans += freq[a];
    }
}

• 循环 n 次
• 每次 freq.find(a) 查找：O(log n)
• 第二步总时间：O(n log n)

总时间复杂度

$$T = O(n \log n) + O(n \log n) = O(n \log n)$$

使用 unordered_map<long long, long long> 的情况

若用 unordered_map 替代 map：

• 平均每次插入/查找：O(1)
• 第一步：O(n)
• 第二步：O(n)
• 总时间复杂度：O(n)（平均情况）
• 最坏情况：O(n²)（hash 冲突严重时）

复杂度对比

容器	第一步	第二步	总复杂度	适用场景
map	O(n log n)			数据量大且要求稳定
unordered_map	O(n)		O(n) 平均	一般情况，性能更好

与暴力算法的对比

暴力算法（两层循环）：

long long ans = 0;
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        if (arr[i] - arr[j] == c) {
            ans++;
        }
    }
}
// 时间复杂度：O(n²)

哈希表算法：

// 时间复杂度：O(n log n) 或 O(n)

数据量验证

对于本题 N ≤ 2×10⁵：

• 暴力算法：(2×10⁵)² = 4×10¹⁰ 次操作 ❌ 会超时
• 哈希表算法：
  • 用 map：2×10⁵ × log(2×10⁵) ≈ 2×10⁵ × 18 ≈ 3.6×10⁶ 次操作 ✓
  • 用 unordered_map：2×10⁵ 次操作 ✓

结论： 哈希表算法能轻松处理最大数据量，而暴力算法会明显超时

---

C++ 实现

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n;
    long long c;
    cin >> n >> c;
    
    map<long long, long long> freq;
    vector<long long> arr(n);
    
    // 第一步：读入数据并记录每个数字的频率
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
        freq[arr[i]]++;
    }
    
    // 第二步：遍历每个B，查找对应的A = B + C
    long long ans = 0;
    for (int i = 0; i < n; i++) {
        long long b = arr[i];
        long long a = b + c;
        // 如果A存在于哈希表中，加上A的频率
        if (freq.find(a) != freq.end()) {
            ans += freq[a];
        }
    }
    
    cout << ans << endl;
    return 0;
}

代码逻辑解释

1. 读入阶段：

   • 读入 n 和 c
   • 读入 n 个数字到数组 arr 中
   • 同时用 map 统计每个数字的出现频率

2. 计算阶段：

   • 遍历数组中的每个数字作为 B
   • 计算需要找的数字 A = B + C
   • 在哈希表中查询 A 是否存在
   • 如果存在，将 A 的频率加到答案中

3. 输出：打印最终答案

关键优化

• ios_base::sync_with_stdio(false); cin.tie(NULL); 加速输入输出
• 使用 map 而不是二维数组循环，避免 O(N²) 的时间复杂度
• 一遍遍历即可完成计算，无需多次查询

---

关键语法详解：freq.find(a) != freq.end()

这行代码的含义

if (freq.find(a) != freq.end()) {
    ans += freq[a];
}

这是在 检查哈希表中是否存在键 a

详细拆解

freq.find(a) 返回什么？

• 找到键 a：返回指向该元素的迭代器
• 未找到键 a：返回 end() 迭代器（指向容器末尾之后的哨兵位置）

freq.end() 是什么？

• 指向 map 容器的末尾之后的位置
• 不指向任何真实元素，仅作为"查询失败"的标志

!= 的含义

freq.find(a) != freq.end()

如果返回的迭代器不等于 end()，说明找到了这个键 a，执行 if 块

三种常见写法对比

方法1：用 find() 和 end()（推荐）

if (freq.find(a) != freq.end()) {
    ans += freq[a];
}

• ✓ 先检查存在性，再访问
• ✓ 不会自动创建新键
• ✓ 最安全的做法

方法2：用 count()（简洁）

if (freq.count(a)) {
    ans += freq[a];
}

• count() 返回 0（不存在）或 1（存在）
• 等价于方法1，代码更简洁
• 也不会创建新键

方法3：直接访问（不推荐）

if (freq[a]) {  // ❌ 有风险
    ans += freq[a];
}

• ❌ 如果键不存在，会自动创建该键并初始化为 0
• 虽然在本题中逻辑还是对的，但会浪费内存
• 不是最佳实践

本题具体例子

数列：1 1 2 3，C = 1

// 哈希表内容：{1: 2, 2: 1, 3: 1}

// 当处理 B = 1 时
a = 1 + 1 = 2
freq.find(2)                    // 查找键 2
↓
找到了！返回指向 (2→1) 的迭代器

freq.find(2) != freq.end()      // 判断：true
↓
ans += freq[2]                  // 执行：ans += 1

---

// 当处理 B = 3 时
a = 3 + 1 = 4
freq.find(4)                    // 查找键 4
↓
没找到！返回 end() 迭代器

freq.find(4) != freq.end()      // 判断：false
↓
不执行 if 块

为什么选择 find() 而不是直接访问？

对比演示：

// 场景：查找键 100（不存在）

// 方法1：find()（推荐）
if (freq.find(100) != freq.end()) { ... }
// 结果：只查询，freq 的大小不变

// 方法3：直接访问（不推荐）
if (freq[100]) { ... }
// 结果：自动创建 freq[100] = 0，freq 的大小 +1
// 额外消耗内存！

结论： 对于纯查询场景（不需要插入新键），find() 是最安全高效的选择！