A-B 数对

标签: #双指针 #二分
原题目: luogu-P1102
简要描述:

这是一个非常经典的算法题目，考察的是对数组特性的利用以及二分查找或双指针算法的掌握。

核心思路转换： 原式 A−B=CA - B = C 可以转换为 A=B+CA = B + C。 这意味着，对于数组中的每一个数 BB，我们需要在数组中寻找有多少个 AA 等于 B+CB + C。

由于数据范围 N≤2×105N \le 2 \times 10^5，暴力 O(N2)O(N^2) 的解法会超时，我们需要 O(Nlog⁡N)O(N \log N) 的解法。

以下是针对该题目的详细解析，包含二分法和双指针法两种实现。

核心预处理：排序

无论使用哪种方法，首先必须对数组进行升序排序。 排序使得数组具有单调性，这是使用二分和双指针的前提。

  • 时间复杂度： O(Nlog⁡N)O(N \log N)

方法一：二分查找法 (Binary Search)

1 算法思路

既然数组已经有序，对于每一个数 a[i]a[i]（将其视为公式中的 BB），我们要找在这个数组中是否存在 a[i]+Ca[i] + C（将其视为 AA），以及它的数量。

我们可以利用 C++ STL 中的 lower_bound 和 upper_bound 函数：

  • lower_bound: 查找第一个 大于等于 目标值的地址。
  • upper_bound: 查找第一个 大于 目标值的地址。

数量计算： 对于每个 a[i]a[i]，目标值 Target=a[i]+CTarget = a[i] + C 的出现次数 = upper_bound(Target) - lower_bound(Target)。

2 代码实现 (C++)

cpp
copy 
        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

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

const int MAXN = 200005;
long long a[MAXN]; // 使用 long long 防止数值溢出，虽然题目说 < 2^30，int 也够，但在计算 count 时必须 long long

int main() {
    int n;
    long long c;
    cin >> n >> c;

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

    sort(a, a + n); // 必须排序

    long long ans = 0; // 注意：答案可能超过 int 范围
    
    for (int i = 0; i < n; i++) {
        long long target = a[i] + c;
        // 在数组中寻找 target 的起始位置和结束位置
        // lower_bound 返回第一个 >= target 的指针
        // upper_bound 返回第一个 > target 的指针
        // 两者相减即为 target 出现的次数
        ans += (upper_bound(a, a + n, target) - lower_bound(a, a + n, target));
    }

    cout << ans << endl;
    return 0;
}

3 复杂度分析

  • 排序： O(Nlog⁡N)O(N \log N)
  • 查找： 循环 NN 次，每次二分查找耗时 O(log⁡N)O(\log N)，总共 O(Nlog⁡N)O(N \log N)。
  • 总复杂度： O(Nlog⁡N)O(N \log N)，可以通过 100%100\% 的数据。

方法二：双指针法 (Two Pointers)

1 算法思路

双指针法利用了数组排序后的单调性。 我们遍历数组中的每个元素 a[i]a[i] 作为 BB，去寻找 AA（即 a[i]+Ca[i] + C）。

因为 a[i]a[i] 是递增的，那么对应的 a[i]+Ca[i] + C 也是递增的。 我们可以维护两个指针 l (left) 和 r (right)：

  • 指针 l 指向第一个 等于 a[i]+Ca[i] + C 的位置。
  • 指针 r 指向第一个 大于 a[i]+Ca[i] + C 的位置。

当 ii 向右移动时，l 和 r 只需要继续向右移动（不需要回头），直到满足上述条件。 对于当前的 a[i]a[i]，满足条件的 AA 的个数就是 r - l。

2 代码实现 (C++)

cpp
copy 
        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

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

const int MAXN = 200005;
long long a[MAXN];

int main() {
    int n;
    long long c;
    cin >> n >> c;

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

    sort(a, a + n);

    long long ans = 0;
    int l = 0, r = 0; // 定义双指针

    for (int i = 0; i < n; i++) {
        long long target = a[i] + c;
        
        // 移动 l 指针，直到 a[l] >= target
        while (l < n && a[l] < target) {
            l++;
        }
        
        // 移动 r 指针，直到 a[r] > target
        // 注意：r 必须从 l 的位置或者是之前的位置继续向后找
        // 实际上由于 target 递增，r 只要接着上次的位置走即可，但为了逻辑严密，r 至少要 >= l
        if (r < l) r = l; 
        while (r < n && a[r] <= target) {
            r++;
        }
        
        // 此时，区间 [l, r) 之间的数都等于 target
        if (a[l] == target) {
            ans += (r - l);
        }
    }

    cout << ans << endl;
    return 0;
}

3 复杂度分析

  • 排序： O(Nlog⁡N)O(N \log N)
  • 指针扫描： 虽然代码里有 while 嵌套，但 i、l、r 三个变量都只从 00 增加到 NN，互不回退。所以扫描部分是线性的 O(N)O(N)。
  • 总复杂度： O(Nlog⁡N)O(N \log N) (瓶颈在排序)。

关键点与避坑指南 (易错点)

  1. 数据类型 (Long Long):

    • 题目中 A,BA, B 和 CC 可以用 int (因为 2302^{30} 刚好在 int 范围内，或者安全起见用 long long 存数值)。
    • 但是，计数器 ans 必须使用 long long。
    • 原因： 如果数组中所有数都相同且 C=0C=0（例如 2×1052 \times 10^5 个 11），那么答案是 N×N≈4×1010N \times N \approx 4 \times 10^{10}，这远远超过了 int 的最大值 (2×1092 \times 10^9)。

  2. 重复数字的处理：

    • 题目要求“不同位置的数字一样的数对算不同的数对”。
    • 上述两种方法（二分法的 upper - lower 和 双指针的区间统计）都天然支持这一点，因为它们计算的是值的出现次数。

  3. 负数情况：

    • 题目保证是“正整数数列”，但如果题目扩展到负数，只要 A−B=CA-B=C 成立，逻辑依然通用。

总结

  • 如果对 STL 熟悉，写二分法代码最短，最不容易出错。
  • 双指针法逻辑更底层，效率略优（省去了 log 的开销，虽然总复杂度阶数一样），是面试中常考的技巧。

你需要我为你解释一下这道题如果用 std::map (哈希表) 做法会有什么优缺点吗？

我写的双指针

基本思路

如果数组里面的元素 没有重复的时候的移动,那么这个时候就不是三指针移动了,简单一点.

  • 固定 head 指针的时候,得到一个tail
  • 如果head+1, 那么新的tail 一定是原来tail的右边,(单调性)
  • 这样就不会反复移动,时间O(n)O(n)
  • 可以证明不会遗漏
    • 因为 删除不会移动没有贡献的元素.(固定tail,或tail的时候)

代码

cpp
copy 
        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

        
#include <bits/stdc++.h>
using namespace std;
const long long maxn = 1e6+5;
long long a[maxn];
long long b[maxn];
long long cnt[maxn];
long long n,c;
int main(long long argc, char const *argv[])
{
  cin >> n >> c;
  for (long long i = 0; i < n; i++)
  {
    cin >> a[i+1];
  }
  sort(a+1,a+1+n);
  b[1] = a[1];
  cnt[1]++;
  long long idx = 1;
  for(long long i = 2;i<=n;i++) {
    if( a[i] == a[i-1]) {
      cnt[idx]++;
    }
    else {
      idx++;
      cnt[idx] = 1;
      b[idx] = a[i];
    }
  }
  // for(long long i =1;i<=idx;i++)
  // {
  //   cout << b[i] << ' ' << cnt[i] << endl;
  // }

  long long h=1,t=2;

  long long ans = 0;
  while(1) {

    if( t > idx || h > idx ) break;

    if( b[t] - b[h] == c) {
      ans += cnt[t] * cnt[h];
      // b[t]不可能再和前面产生贡献了
      t++;
    }
    else if (b[t] - b[h] > c) {
      h++;
    }
    else if ( b[t] - b[h] < c) {
      t++;
    }
  }
  cout << ans << endl;

  return 0;
}

你的这份代码写得非常有意思且高效！你没有使用常规的“在原数组上跑双指针”或者“二分查找”，而是先做了一个**数据离散化（或称为“去重+计数”）**的处理，然后再对去重后的数组进行双指针扫描。

这种做法思路非常清晰，将“数值”和“该数值出现的次数”分离开来，逻辑上更符合组合数学的乘法原理。

以下是对你代码的详细解析：

1 核心思路分析

你的解法可以分为三个阶段：

  1. 排序：将乱序数组变为有序。
  2. 压缩（去重+计数）：将数组转化为“数值数组 b”和“频率数组 cnt”。
    • b[i] 存储第 i 小的唯一数值。
    • cnt[i] 存储 b[i] 在原数组中出现的次数。
  3. 双指针查找：在 无重复元素 的 b 数组上寻找差值为 CC 的对子，一旦找到，答案加上 cnt[t] * cnt[h]。

2 代码分步解析

第一步：输入与排序

cpp
copy 
        
1
2
3
4

        cin >> n >> c;
// ... 读取 a 数组 ...
sort(a+1, a+1+n);

这是标准操作，确保后续处理基于有序序列。

第二步：数组压缩 (Dedup & Count)

这是你代码中最亮眼的部分：

cpp
copy 
        
1
2
3
4
5
6
7
8
9
10
11
12
13

        b[1] = a[1];
cnt[1]++;
long long idx = 1;
for(long long i = 2; i <= n; i++) {
    if(a[i] == a[i-1]) {
        cnt[idx]++; // 如果当前数等于前一个数，当前唯一值的计数+1
    } else {
        idx++;      // 发现新数值，指针后移
        cnt[idx] = 1; // 初始化新数值的计数
        b[idx] = a[i]; // 记录新数值
    }
}

例子演示： 假设输入 1 1 2 3 (且 C=1)。 经过这一步后：

  • b 数组（唯一值）：[1, 2, 3]
  • cnt 数组（对应数量）：[2, 1, 1] （即 1 有 2 个，2 有 1 个，3 有 1 个）
  • idx = 3

第三步：双指针计算

cpp
copy 
        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

        long long h=1, t=2; // h(head)指向被减数位置，t(tail)指向减数位置
while(1) {
    if(t > idx || h > idx) break; // 边界检查

    long long diff = b[t] - b[h];
    
    if(diff == c) {
        ans += cnt[t] * cnt[h]; // 核心公式：组合数学乘法原理
        t++; // 移动 t 继续寻找
    }
    else if (diff > c) {
        h++; // 差太大了，减数(b[h])需要变大，h右移
    }
    else if (diff < c) {
        t++; // 差太小了，被减数(b[t])需要变大，t右移
    }
}

逻辑分析：

  • 当 b[t] - b[h] == c 时，说明找到了满足 A−B=CA - B = C 的数值对。
  • 因为原数组可能有重复，这里直接用乘法：A的数量 ×\times B的数量，一步到位算出了所有组合。
  • 关于指针移动：你选择了 t++。由于 b 数组是严格单调递增的，当 b[t] 变大后，差值肯定会 >C>C，所以在下一次循环中会进入 else if (diff > c) h++ 的分支。这在逻辑上是完全正确的（虽然同时 t++, h++ 会稍微快那么一点点，但你的写法完全没问题）。

3 代码的优缺点与潜在问题

优点：

  • 逻辑清晰：通过 cnt 数组处理重复元素，避免了常规双指针在处理重复元素时需要写很多 while 循环来跳过相同元素的麻烦。
  • 效率高：时间复杂度主要取决于排序 O(Nlog⁡N)O(N \log N)，后续压缩和扫描都是线性 O(N)O(N)。

潜在风险 (Edge Cases)：

  1. 关于 C=0C=0 的情况：
    • 题目说明中提到 C≥1C \ge 1，所以你的 h=1, t=2 是安全的。
    • 如果题目允许 C=0C=0，你的代码将输出 0。因为 t 永远从 h+1 开始，b 又是严格递增的，b[t] - b[h] 永远 >0>0。
    • 修正建议：如果为了通用性（兼容 C=0C=0），可以设 h=1, t=1，并且加个特判 if(c==0) 则只算 cnt[i]*(cnt[i]-1)（但这题不需要）。
  2. 单一元素情况：
    • 如果输入 5 1 且数组为 1 1 1 1 1。
    • 压缩后 idx=1。
    • h=1, t=2。
    • if (t > idx) 立即触发 break。
    • 输出 0。正确（因为没有差值为1的对）。

4 一个小的改进建议

虽然逻辑是对的，但是 while(1) 配合内部 break 稍微有点不优雅。另外，当 b[t] - b[h] == c 时，既然 b 数组没有重复数字，那么当前的 b[h] 也不可能再和后面的 b[t] 配对成功了，所以其实 h 也可以一起往后移。

微调后的循环部分如下：

cpp
copy 
        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

            long long h = 1, t = 1; // 从1开始更通用，虽然题目C>=1导致t=2也可以
    // 实际上对于C>=1，t从1开始也会迅速被 diff < c 推到 2
    
    while (t <= idx && h <= idx) {
        long long diff = b[t] - b[h];
        if (diff == c) {
            ans += cnt[t] * cnt[h];
            t++;
            h++; // 两个都移，因为数值唯一，当前h和t都已利用完毕
        } else if (diff > c) {
            h++;
        } else {
            t++;
        }
    }

总结

你的代码是一个非常优秀的 AC 代码。利用离散化思想处理重复元素，不仅让双指针逻辑变得极其清爽，也避免了处理重复元素时容易出现的边界 bug。完全可以作为这道题的标准题解之一！

题目