洛谷-P1102 A-B 数对题解

题目链接：https://www.luogu.com.cn/problem/P1102

题解：统计满足 A - B = C 的数对个数

题目大意

给定一个长度为 N 的正整数序列和一个正整数 C，求有多少对 (i, j)（i ！= j，位置不同即视为不同）满足：

Ai-Aj=C

注意：即使数值相同，只要位置不同就算作不同的数对。

解题思路

转化问题

将等式变形：

Ai = Aj + C

也就是说，对于每个元素 x，我们想知道序列中有多少个元素等于 x + C。

于是问题转化为：对每个 x，统计 x + C 出现的次数，并累加。

方法一：排序 + 双指针

核心思想

先将数组排序；
使用两个指针 l 和 r，维护 nums[r] - nums[l] == C 的窗口；
当找到一组相等差值时，统计连续相同值的个数，利用乘法原理计算所有有效数对。

为什么可以这样做？
因为排序后，所有相同的数会相邻，且若 nums[r] - nums[l] == C，那么 nums[l] 所有重复项与 nums[r] 所有重复项都能组成合法数对。

算法步骤

读入数据并排序；
初始化双指针 l = 0, r = 0；
移动 r 直到 nums[r] - nums[l] >= C；
如果差值恰好等于 C：统计 nums[l] 连续出现的次数 d1；统计 nums[r] 连续出现的次数 d2；累加 d1 * d2 到答案；将 l 向右移动一位（跳过已处理的重复块）；
否则（差值 > C），只移动 l；
重复直到 r 越界。

注意：每次处理完一个 (l, r) 匹配块后，l++ 是为了进入下一个不同的 nums[l] 值。

正确性说明

排序不改变数对总数（因为题目允许任意位置组合，不要求顺序）；
对于每一对不同的值 (x, x+C)，它们在排序后形成连续块；
若 x 出现 d1 次，x+C 出现 d2 次，则共有 d1 × d2 个合法数对（每个 x 可与每个 x+C 配对）；
双指针确保每对 (x, x+C) 只被统计一次。

代码解析

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

typedef long long ll;
vector<ll> nums;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n;
    ll c;
    cin >> n >> c;
    nums.resize(n);
    for (int i = 0; i < n; i++)
        cin >> nums[i];
    
    sort(nums.begin(), nums.end()); // 关键：排序
    
    int l = 0, r = 0;
    ll ans = 0;
    
    while (r < n) {
        // 扩展右指针，直到差值 >= c
        while (r < n && nums[r] - nums[l] < c)
            r++;
        
        // 如果正好等于 c
        if (r < n && nums[r] - nums[l] == c) {
            ll d1 = 1, d2 = 1;
            
            // 统计左边相同值的个数
            while (l < r && nums[l + 1] == nums[l]) {
                d1++;
                l++;
            }
            
            // 统计右边相同值的个数
            while (r < n - 1 && nums[r + 1] == nums[r]) {
                d2++;
                r++;
            }
            
            ans += d1 * d2; // 乘法原理
        }
        
        l++; // 移动左指针，处理下一个值
    }
    
    cout << ans;
    return 0;
}

边界处理

l < r：防止 l 超过 r（当 c = 0 时需特别注意，但本题 C ≥ 1，所以安全）；
r < n - 1：避免越界访问 nums[r+1]。

⚠️ 注意：题目中说明 C ≥ 1，因此 不会出现 A - B = 0 的情况，即无需考虑 i = j 或相同元素相减，简化了问题。

复杂度分析

时间复杂度：O(N log N)主要开销在排序，双指针扫描为 O(N)。
空间复杂度：O(N)存储数组。

对于 N <=2 * 10^5，完全可行。

方法二：哈希表法

unordered_map<ll, ll> cnt;
for (ll x : nums) cnt[x]++;

ll ans = 0;
for (auto &p : cnt) {
    ll x = p.first;
    if (cnt.count(x + c)) {
        ans += p.second * cnt[x + c];
    }
}