P1102 A-B数对 题解

· · 题解

P1102 A-B数对 题解

题目传送门

简化一下题意：给你一个长度为 n 的数组 nums 还有 target，要求你找出数组 nums 中相减的差为 target 的数。

这题不明显就是双指针吗，为什么题解区里面都是用 map 暴力打出来的？

这里附上一篇用双指针的做法。

Solution：

首先我们用 sort 函数排序一下，然后定义一个 left 指针，我这边又定义了两个 right 指针方便思考和理解，最后只用一个 for 查找。

上代码吧，这么思路清晰的代码一定很好理解

Code：

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 10;
int n, c;
int arr[N];

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

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

    sort(arr + 1, arr + 1 + n);
    int left = 1, right1 = 1, right2 = 1;
    long long ans = 0;

    for (left = 1; left <= n; left++) {
        // 找到第一个满足条件的right1
        while (right1 <= n && arr[right1] - arr[left] <= c) {
            right1++;
        }
        // 找到第一个满足条件的right2
        while (right2 <= n && arr[right2] - arr[left] < c) {
            right2++;
        }

        // 如果满足条件，计算符合要求的数对
        if (arr[right2] - arr[left] == c && arr[right1 - 1] - arr[left] == c && right1 - 1 >= 1) {
            ans += right1 - right2;
        }
    }

    cout << ans;
    return 0;
}

这是一个标准的双指针题解，目前没看到几篇用双指针做的，都是用 map 暴力做的，为什么他们没超时？