CCF CSP的第一题，向来是给考生"练手"和"送分"的。但说句实在话，很多人第一次考CCF，恰恰就栽在这道"送分题"上——不是不会做，而是读题太急，把"相邻数对"理解成了"数组里位置相邻的两个数"，结果样例都过不了，心态直接崩了。
我拿2014年9月的这道CCF201409-1 相邻数对来当例子，把这类型"序列处理"题目的标准解法、思考路径和那些年我们一起踩过的坑，一次说清楚。这道题的原题要求是：给定n个不同的整数，问这些数中有多少对整数，它们的值正好相差1。注意，是值相差1，不是位置相邻。题目难度不大，但特别适合用来理解"序列处理"中一个核心思想：怎么把"双重循环暴力"优化成"一次遍历搞定"。
这篇文章适合所有准备CCF CSP认证的考生、参加算法竞赛入门的新手，以及想复习基础数据结构与算法的人。我会从题目本质、暴力思路、哈希优化、代码实现、易错点排查这几个维度展开，最后再聊聊同一类题的变种怎么举一反三。
1. 题目到底在考什么：兼谈"序列处理"的通用套路
1.1 原题要求与样例剖析
先看题目怎么说的。输入第一行是整数n，表示给定整数的个数，n不会太大，我记得当年范围是1 ≤ n ≤ 1000。第二行是n个互不相同的整数，每个数的绝对值不会很大。要求输出一个整数，表示这n个数里，有多少对数的值正好相差1。
样例输入是这样的：
6 10 2 6 3 7 8样例输出是3。为什么是3？因为这6个数里，相差1的数对有这三组：(2, 3)、(6, 7)、(7, 8)。注意(10, ?)没有10旁边的9或11，所以不算。(2, ?)也没有1或3？不，2旁边有3，所以(2,3)算一对。这样数下来正好3对。
我第一次做这道题的时候，差点把(6, 7)和(7, 8)数成两组，然后就以为答案是2，后来才反应过来，7可以和左右两边各形成一对，这是完全合法的。也就是说，同一个数可以参与多对"相邻数对"，题目里并没有限制一个数只能用一次。
1.2 这道题背后的核心考点
CCF第一题通常不考复杂算法，但一定会考一个基础能力：能不能把问题"翻译"成程序逻辑。这道题翻译过来就是：给定一个集合（因为数互不相同），统计集合中所有满足|a - b| == 1的有序元素对数量。
这里藏着一个关键信息——"n个不同的整数"。这个条件太重要了。如果没有这个条件，比如数组里有重复数字，那么统计差值1的数对时就要考虑相同数值可能出现多次的情况，处理起来会麻烦很多。CCF第一题为什么会把这个条件写出来？就是为了让你可以直接"无脑枚举"，不需要先做去重或计数。
从算法设计的角度看，这道题考察了两个层次的"序列处理"思维：
第一层，暴力枚举。双重循环把所有数对检查一遍，符合条件就计数。这个思路直接、不容易错，适合考试时求稳。
第二层，空间换时间。利用"值域范围有限"的特点，开一个标记数组或哈希表，先标记所有出现过的数，再遍历每个数检查它的x-1或x+1是否出现过，把时间复杂度从O(n^2)降到O(n)。
1.3 解题前一定要做的三件事
不管你用哪种方法，下笔之前，我强烈建议按这个顺序过一遍：
第一，确认输入范围。n最多1000时，暴力完全没问题；但如果n到了10^5级别，暴力双重循环就是灾难。这是做所有序列处理题的第一步：算复杂度，决定方案。
第二，确认数值范围。如果数值在0~10000这种可控范围内，开数组标记是首选；如果数值可以达到10^9甚至更大，开数组就不现实了，必须用unordered_map或set这类哈希结构。
第三，确认有无重复。题目说"不同的整数"，你可以放心用集合思想；如果没有这句话，你得先想清楚重复值要怎么处理。
这一步想清楚了，后面的代码基本就是水到渠成。
2. 三种解题思路对比：暴力、排序、哈希
2.1 暴力双重循环：最稳妥的"保底方案"
暴力法的思路非常直白：枚举所有可能的数对(a[i], a[j])，其中i < j，判断它们的差的绝对值是否为1。如果是，答案加1。
#include <iostream> #include <cmath> using namespace std; int main() { int n; cin >> n; int a[1005]; for (int i = 0; i < n; i++) { cin >> a[i]; } int ans = 0; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { if (abs(a[i] - a[j]) == 1) { ans++; } } } cout << ans << endl; return 0; }这个代码的时间复杂度是O(n^2)，空间复杂度是O(n)（只存了数组）。n是1000时，内层循环最多跑约50万次，对现代CPU来说就是一瞬间的事。CCF评测系统给第一题的时间限制通常是1秒，这个复杂度完全够用。
为什么说这是"保底方案"？因为它逻辑最简单，几乎不可能写错。考试的时候，如果一时想不出更优解法，直接暴力拿满分，不丢人。算法竞赛里有一句老话："能过的暴力就是好算法。"尤其是第一题，它的目的就是让你拿分，不是让你炫技。
2.2 排序后扫描：把"无序"变"有序"
第二种思路是先把数组排序，然后只检查相邻元素。为什么排序后只需要检查相邻的？因为如果两个数相差1，它们在排序后的数组中一定是紧挨着的——不可能中间还隔着一个数，却仍然相差1。
#include <iostream> #include <algorithm> using namespace std; int main() { int n; cin >> n; int a[1005]; for (int i = 0; i < n; i++) { cin >> a[i]; } sort(a, a + n); int ans = 0; for (int i = 0; i + 1 < n; i++) { if (a[i + 1] - a[i] == 1) { ans++; } } cout << ans << endl; return 0; }排序法的时间复杂度是O(n log n)，比暴力的O(n^2)好，但比接下来的哈希法差。不过它有个额外的好处：代码极短，而且不需要额外开"标记数组"，对空间的占用更小。如果题目后续要求你"输出这些数对"，排序法天然就能按顺序输出，非常方便。
我自己很喜欢这种"先排序，再相邻比较"的套路，因为它在很多题目里都能复用。比如"给定一个数组，找出差值最小的数对"，不也是先排序再扫一遍吗？序列处理的常用技巧其实就那几个，排序永远是排第一位的。
2.3 哈希标记法：最优解，也是"正解"
第三种思路是"空间换时间"的经典应用：用一个标记数组或者哈希集合，记录哪些数出现过。然后遍历原数组，对每个数x，检查x-1和x+1是否在集合里。如果在，说明构成一个合法数对。
#include <iostream> #include <unordered_set> using namespace std; int main() { int n; cin >> n; unordered_set<int> s; int a[1005]; for (int i = 0; i < n; i++) { cin >> a[i]; s.insert(a[i]); } int ans = 0; for (int i = 0; i < n; i++) { if (s.count(a[i] + 1)) { ans++; } } cout << ans << endl; return 0; }为什么只检查a[i] + 1，不检查a[i] - 1？因为数对是无序的。如果检查了a[i] + 1，那么当遍历到a[i] + 1这个元素时，它会检查(a[i] + 1) + 1，不会重复统计刚才那对。所以每对数对只会被统计恰好一次。
当然，如果你用unordered_set，需要注意头文件是#include <unordered_set>，C++标准里它是C++11才有的。有些老旧的评测环境如果不支持C++11，可以用set替代，但set底层是红黑树，插入和查找都是O(log n)，整体复杂度变为O(n log n)，依然优秀。不过就这道题的数据范围而言，set和unordered_set实测性能差异不大。
2.4 三种方案横向对比
| 方案 | 时间复杂度 | 空间复杂度 | 代码长度 | 适用场景 |
|---|---|---|---|---|
| 暴力双重循环 | O(n^2) | O(n) | 极短 | n ≤ 1000，求稳 |
| 排序后扫描 | O(n log n) | O(1) | 极短 | 任意n，需要输出数对 |
| 哈希标记 | O(n) | O(n) | 短 | n较大，追求最优 |
从CCF历年的出题习惯来看，第一题的数据范围往往不会太大，三种方法都能过。但我依然建议你掌握哈希标记法，因为它是"序列处理"里最核心的思想之一——用额外的存储空间来减少不必要的重复计算。后面刷到更难的题，比如"两数之和""最长连续序列"，你会频繁用到这个思路。
3. 代码实现细节与常见写法误区
3.1 数组开多大的问题
使用标记数组时，最常见的翻车点是数组越界。如果题目数值范围是0 ≤ a[i] ≤ 10000，你开一个大小为10005的数组就行。但要注意，如果你检查a[i] + 1，当a[i]恰好是10000时，a[i] + 1是10001，数组至少要开到10002才安全。
有一种更稳妥的做法是用unordered_set。它能动态扩展，不会越界，也不要求你事先知道具体数值范围。虽然比数组稍微慢一点，但对这种题目来说根本没区别。我在实际做题时，如果数据范围明确，我倾向开数组，简单直接；如果数据范围模糊或者很大，我就用unordered_set。
3.2 负数的处理
这道题的数可能是负数吗？题目通常不会明说"非负"，所以你要做好负数出现的准备。如果用数组当标记，会有一个大坑：下标不能是负数。解决办法是先找到最小值，把所有数做一个偏移；更简单的办法是直接用unordered_set，它天然支持负数。
很多第一次参加CCF的同学，看到样例全是正数，就默认所有测试点都是正数。这是很危险的惯性思维。评测数据里往往隐藏着"边界数据"，比如负数、最大值、最小值、只有一个数等等。读题时看到"整数"两个字，就要默认它可能包含负数。
3.3 输入输出的效率细节
CCF这类题目对IO效率要求不高，cin/cout一般够用。但如果你在刷题时遇到大规模输入，记得加上这两行：
ios::sync_with_stdio(false); cin.tie(0);作用分别是取消C和C++的输入输出流同步、解除cin和cout的绑定，可以显著加快输入输出速度。不加这两行，在数据量大的时候可能超时；加了之后，cin的速度基本能赶上scanf。
有些人会建议直接用scanf和printf，也没问题。个人习惯用cin+cout，因为写起来舒服，还能利用string等C++特性。但务必记得加那两行优化，这是很多老手不会专门告诉你，但自己一定会写的细节。
3.4 Python版本的写法
如果你用Python刷题，代码会更简洁。这里给出两种：一种用set哈希，一种用排序。
n = int(input()) a = list(map(int, input().split())) s = set(a) ans = 0 for x in a: if x + 1 in s: ans += 1 print(ans)Python的set底层也是哈希表，in操作的均摊复杂度是O(1)。整个代码的时间复杂度是O(n)，空间复杂度是O(n)。对于这道题来说，Python完全够用。
不过要注意，CCF CSP认证的老版本评测环境可能是Python 2，那就要把input()换成raw_input()。现在应该都是Python 3了，这个问题影响不大，但如果你在练习旧题，可以先确认评测机版本。
4. 易错点与排查技巧实录
4.1 把"值相差1"理解成"位置相邻"
我前面反复强调这一点，因为它真的是新手重灾区。题目叫"相邻数对"，但这个"相邻"指的是数值上相差1，而不是数组下标上紧挨着。如果按位置相邻来理解，样例10 2 6 3 7 8里，只有(6, 7)？不，位置相邻是(2, 6)差4、(6, 3)差3、(3, 7)差4、(7, 8)差1，只有一对。但样例答案是3，所以明显不对。
怎么避免这个坑？拿到题目后，先别看标题，先读题面。看到"它们的值正好相差1"这种表述，就要明确：这是对数值关系的描述，不是对位置的描述。标题里的"相邻"是借用了"数值相邻"的说法，容易误导人。
4.2 哈希法重复计数
用哈希法时，如果对每个x同时检查x-1和x+1，每个数对会被统计两次。举个例子，2和3是一对，遍历到2时会发现3存在，计数加1；遍历到3时会发现2存在，又加1。最终答案就翻倍了。
解决办法有两个：只检查x+1（推荐），或者最后把答案除以2。我更推荐前者，因为逻辑更清晰，也不用担心奇偶问题。
如果你在自测时发现答案恰好是预期值的两倍，不用怀疑，一定是这个原因。
4.3 暴力法忘记j从i+1开始
暴力法里，内层循环的起点必须是j = i + 1，不能是0。如果把j从0开始，会重复统计相同数对，而且还会把i == j的情况也算进去——即一个数和它自己相差0，不等于1，所以不会影响答案，但会平白多跑很多没用的循环。虽然不影响正确性，但显得不专业。更关键的是，如果题目不是差1而是差0，那么i == j会被错误计数，到时候查bug查到怀疑人生。
4.4 边界数据自测清单
写完代码，我建议你至少自测这五组数据：
输入： 1 5 输出： 0只有一个数，必然没有数对，答案是0。
输入： 2 1 2 输出： 1最小规模的有效输入，答案是1。
输入： 2 1 3 输出： 0差值为2，不是1，答案是0。
输入： 5 -1 0 1 2 3 输出： 4这组数据同时测了负数、连续序列、多个数对参与的情况。(-1,0)、(0,1)、(1,2)、(2,3)，一共4对。
输入： 4 100 200 300 400 输出： 0全都是远距离差值，答案是0。这组数据的意义在于：你的代码不应该因为数值大而数组越界或出现其他异常。
这五组过了，基本上就能稳拿100分。
5. 从"相邻数对"到"序列处理"的举一反三
5.1 变种一：差值为k的数对
原题要求差1，如果改成"差值为k"呢？思路完全一样，只是把a[i] + 1改成a[i] + k而已。如果是"差值绝对值不超过k"，那就需要稍微改一下判断条件，可能要配合排序和双指针，但核心思想还是处理序列元素之间的数值关系。
这类题的价值在于，让你理解"查值"操作的重要性。当你需要频繁判断"某个数是否在集合中"时，哈希表就是你的第一选择。
5.2 变种二：不要求互不相同的数
如果题目去掉"n个不同的整数"这个条件，允许重复，那情况就变了。比如数组[2, 2, 3, 3]，差值为1的数对有几对？
如果没有去重，(2,3)这个组合里，两个2和两个3可以组成4对不同的下标对。这时，你需要先统计每个数出现的次数，然后对于每个x，答案累加count[x] * count[x+1]。这已经进阶到"哈希表存频率"的层次了。CCF第一题不会这么刁难你，但第二、第三题很可能出现。
5.3 变种三：输出具体的数对
有时候题目不要求计数，而是要求输出满足条件的数对。这时排序法的优势就体现出来了：排序后，只需一次遍历，凡是a[i + 1] - a[i] == 1，就直接输出这对。而且输出的数对天然有序，不需要额外排序。
如果你用哈希法来输出，就得额外存储"配对关系"，代码会复杂不少。所以遇到"输出数对"的题目，优先考虑排序，而不是哈希。
5.4 刷题建议：从CCF第一题到更广阔的题目
CCF认证的难度是循序渐进的，第一题送分，第二题模拟或简单数据结构，第三题大模拟，第四第五题才是真正拉开差距的题。如果你想系统地准备，建议按这个路径来：
先把近五年的第一题全刷一遍，每道题都用暴力和优化两种方法写一遍。这一步能帮你建立"序列处理"的基本功——数组、排序、哈希、差分，这些基础操作在后续所有题目里都会反复用到。第一题都写不利索，后面的题根本没法做。
然后是第二题。CCF第二题的套路很固定：字符串处理、日期计算、集合去重、简单模拟。你会发现，第二题本质上还是在做"序列处理"，只是形式更花哨一些。
个人经验是：认证前两周，每天刷一套真题，重点看第一题能不能做到10分钟之内从读题到AC。做到这个速度，第一题的分数就稳了。剩下时间都砸在第二题上，争取第二题也能拿满分，这样前两题加起来就有200分，通过认证基本没有悬念。
写在最后的经验之谈
这道题我前前后后刷过三遍，每次都有新收获。第一遍用暴利枚举过的，纯粹为了AC；第二遍看题解发现可以用sort，感叹代码真短；第三遍才真正理解哈希标记的精妙之处——它把"判断两个数是否相关"变成了"查询一个数是否存在"，这两种思维的差别，就是初级码农和工程老手的分水岭。
还有一个细节想提醒大家：CCF评测时，如果代码超时或数组越界，返回的是"运行错误"而非"答案错误"。如果你提交后看到Runtime Error，别慌，先把数组范围加大，把unordered_set换成数组，大概率就能解决。如果看到Time Limit Exceeded，优先检查是不是哪里写了个死循环，其次才是考虑换更优的算法。
最后再分享一个我自己刷题的小习惯：每做完一道题，不管AC没有，都去讨论区看看别人的题解。哪怕你已经用最优解做出来了，也会发现有人用了更刁钻的方法——比如这道题有人用bitset做，有人用差分数组做，每个思路都是对"序列处理"这一主题的一次加深理解。看得多了，再遇到新题，你脑子里就会自动涌现出好几种可选方案，那时候你就不会再怕任何CCF第一题了。
