# P1102 A-B 数对

## 题目背景

出题是一件痛苦的事情！

相同的题目看多了也会有审美疲劳，于是我舍弃了大家所熟悉的 A+B Problem，改用 A-B 了哈哈！

## 题目描述

给出一串正整数数列以及一个正整数 $C$，要求计算出所有满足 $A - B = C$ 的数对的个数（不同位置的数字一样的数对算不同的数对）。

## 输入格式

输入共两行。

第一行，两个正整数 $N,C$。

第二行，$N$ 个正整数，作为要求处理的那串数。

## 输出格式

一行，表示该串正整数中包含的满足 $A - B = C$ 的数对的个数。

##输入输出样例#1

###输入#1

```
4 1
1 1 2 3
```

###输出#1

```
3
```

## 说明/提示

对于 $75\%$ 的数据，$1 \leq N \leq 2000$。

对于 $100\%$ 的数据，$1 \leq N \leq 2 \times 10^5$，$0 \leq a_i <2^{30}$，$1 \leq C < 2^{30}$。

2017/4/29 新添数据两组

代码如下：

import sys
from collections import defaultdict

def main():
    data = sys.stdin.read().split()
    n = int(data[0])
    c = int(data[1])
    a = list(map(int, data[2:2+n]))
    
    freq = defaultdict(int)
    for num in a:
        freq[num] += 1
        
    ans = 0
    if c == 0:
        for num, cnt in freq.items():
            ans += cnt * (cnt - 1)
    else:
        for num, cnt in freq.items():
            if num + c in freq:
                ans += cnt * freq[num + c]
                
    print(ans)

if __name__ == "__main__":
    main()

使用了哈希表统计每个数字出现的次数。
然后分类计算：
C = 0时：每个数字 x能组成的有效数对数为 cnt[x] × (cnt[x] - 1)。
C ≠ 0时：对每个数字 x，若 x + C存在于哈希表中，则数对数为 cnt[x] × cnt[x + C]。

此方法时间复杂度为 O(N)