相邻数对

形式化题目

给定 $n$ 个互不相同的非负整数，统计其中有多少对数值正好相差 $1$ 的数对。

思路

先看直接枚举所有下标对的做法：

cpp

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-31 16:21
 * update_at: 2026-08-17 22:53
 */
// brute.cpp：小数据暴力解，枚举所有下标对并检查数值差。
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

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

    int answer = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (abs(numbers[i] - numbers[j]) == 1) {
                answer++;
            }
        }
    }

    cout << answer << '\n';
    return 0;
}

它需要 $O(n^2)$ 次比较。由于数值只关心相差 $1$ ，可以先排序。排序后，若两个数值相差 $1$ ，它们一定在有序数组中相邻；反之，有序数组中相邻元素差为 $1$ 时，这一对就是答案中的合法数对。

因此从左到右检查 numbers[i] - numbers[i-1] == 1 即可。题目保证数值互不相同，所以不会出现重复计数。

样例演示

样例输入 $10, 2, 6, 3, 7, 8$ 排序后为 $2, 3, 6, 7, 8, 10$ ：

相邻数对	差值	计数
(2, 3)	1	1
(3, 6)	3	1
(6, 7)	1	2
(7, 8)	1	3
(8, 10)	2	3

三个差值恰好为 1 的相邻对对应 $(2,3)$ 、 $(6,7)$ 、 $(7,8)$ ，答案为 3。

代码

cpp

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-31 16:21
 * update_at: 2026-08-17 22:53
 */
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

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

    sort(numbers.begin(), numbers.end());

    int answer = 0;
    for (int i = 1; i < n; i++) {
        if (numbers[i] - numbers[i - 1] == 1) {
            answer++;
        }
    }

    cout << answer << '\n';
    return 0;
}

复杂度

排序时间复杂度为 $O(n\log n)$ ，扫描复杂度为 $O(n)$ ，总时间复杂度为 $O(n\log n)$ ；额外空间复杂度为 $O(n)$ 。

总结

当目标只由数值大小关系决定时，排序可以把任意位置的配对关系转化为相邻位置的局部检查。这里“相差 1”的数在排序后必然相邻，因此只需线性扫描一次。

目录

形式化题目

思路

样例演示

代码

复杂度

总结