开局先说实话“A-B数对”这道题本身不难题意一句话就能说清但它是我见过的“看起来简单翻车率却极高”的一类C语言入门算法题。很多人在PTA、洛谷或者学校OJ上第一次遇到它顺手写个双重循环样例一跑发现结果对自信提交然后收获一个红色的超时。也有人优化了排序、二分、哈希都上了结果在C0的测试点翻车或者在负数的数据上莫名其妙的WA答案错误。这篇文章不打算只贴一份能过的代码而是把我从暴力解法一路走到排序二分、再走到手写哈希表的完整思路以及过程中踩过的坑全部摊开来讲一遍。适合正在学C语言、刚接触算法题的读者也适合那些代码能过但没想明白“为什么这么写”的同学。1. 题目到底在算什么东西从“数对”二字说起1.1 题意拆解A-BC 和 ABC 是一回事有一组数给定一个整数C问你一共有多少个数对(i, j)满足第i个数减第j个数等于C。用数学式表达就是A[i] - A[j] C这里说的“数对”指的是两个元素注意它不是指元素值相等就算一对而是指数组里不同位置的两个数。举例来说数组是 [2, 3, 5]C2那么满足条件的有 3 - 2 2 和 5 - 3 2 这两对。如果你把式子移项A[i] - A[j] C 就等价于 A[i] A[j] C也等价于 A[j] A[i] - C。也就是说只要枚举其中一个数找另一个数就行。很多同学在做这一题的时候脑袋里想的是“差为C的两个数”但写代码时却把简单的数学表达式搞混了。我见过有人写if (a[i] - a[j] C) 结果用了双重循环也有人把条件写成 a[i] C a[j]方向搞反样例直接不对。这里最好一开始就明确枚举谁、找谁。1.2 最容易理解错的两个细节重复值和负数第一个细节是重复值。数组里有多个相同的数时它们对应的下标不同所以它们参与组成的数对都要算进去。比如数组 [1, 1, 3]C2那么 3 - 1 2 算两对因为有两个1每个1都和一个3组成一个合法数对。有些同学排序后给数组去重结果答案直接少了一半这是非常典型的错法。第二个细节是负数。C是题目给定的常数它可能是正数、负数或者0。很多人默认数组元素都是非负整数直接拿哈希或者排序的思路写结果遇到负数数据就挂了。比如数组 [-2, 0, 2]C-2满足 A - B -2 的数对有-2 - 0 -20 - 2 -2共两对。如果你做的是“枚举一个数在数组里二分查找另一个数”这条路对负数没有任何问题只要比较函数写得正确就行。把这两个细节记在脑子里再看下面的优化过程你就知道哪些坑是必须绕开的。2. 第一版方案暴力双重循环为什么必然会超时2.1 暴力代码谁都能三分钟写出来的版本先看看最简单的实现代码核心就一个双重循环。假如数组有n个元素#include stdio.h int main() { int n, c; int a[100005]; long long ans 0; scanf(%d %d, n, c); for (int i 0; i n; i) { scanf(%d, a[i]); } for (int i 0; i n; i) { for (int j 0; j n; j) { if (a[i] - a[j] c) { ans; } } } printf(%lld\n, ans); return 0; }这段代码逻辑完全正确尤其适合拿来对拍、验证后面优化版本的正确性。它的时间复杂度是O(n²)因为两层循环把每一对元素都检查了一遍。2.2 实测一把N10^5 时双重循环到底跑了多久我当年第一次交这个版本是在数据规模n最大10^5的OJ上。当时想着C语言跑得快双重循环应该没问题结果超时到怀疑人生。我们来估算一下n100000时双重循环总共要执行大约10^10次减法运算和比较运算。即使你的机器一秒能跑10^8次简单运算10^10这个量级也至少要几十秒OJ普遍限时1秒这显然过不去。还有一个容易被忽略的点双重循环里如果还带着scanf和printf那IO开销会进一步拖慢程序。所以暴力版本唯一的用途就是“验证思路”不是“提交答案”。3. 排序加二分C语言选手最顺手的优化路径3.1 qsort 排序细节比较函数别用减法既然双重循环太慢那就得换思路。我们要找的是“一个数等于另一个数加C”的配对关系如果能提前把数组排好序那么对于每一个数x只需要在有序数组里查找xC存不存在、存在几个。整体复杂度可以降到O(n log n)这是排序加二分的思想。C语言排序首选qsort。但这里有个大坑很多教程教人写比较函数时直接返回两个数的差比如int cmp(const void *a, const void *b) { return *(int *)a - *(int *)b; }在元素是int且差值不大的情况下这段代码可以用。但如果差值超出int范围或者以后你把数组改成long long减法结果就会溢出导致排序出错。正确的写法是改写为“大于返回1小于返回-1等于返回0”的形式int cmp(const void *a, const void *b) { long long x *(const long long *)a; long long y *(const long long *)b; return (x y) - (x y); }这种写法不会溢出而且对负数也天然正确。我建议不管题目数据范围多大养成这个习惯能省掉很多莫名其妙的WA。3.2 手写 lower_bound 与 upper_bound而不是搜标准库C语言不像C有现成的lower_bound和upper_bound函数可以用所以需要自己手写二分查找。这里要查的是“xC这个值在有序数组里出现的次数”更准确地说要找到第一个大于等于xC的位置和第一个大于xC的位置两个位置的下标差就是xC的出现次数。手写二分的关键是边界条件。我常用的写法是左闭右开区间也就是用两个变量l和r表示[l, r)这个查找范围。查找lower_bound的代码是这样int lower_bound(long long arr[], int n, long long key) { int l 0, r n; while (l r) { int mid l (r - l) / 2; if (arr[mid] key) { r mid; } else { l mid 1; } } return l; }upper_bound的代码只是把arr[mid] key改成arr[mid] keyint upper_bound(long long arr[], int n, long long key) { int l 0, r n; while (l r) { int mid l (r - l) / 2; if (arr[mid] key) { r mid; } else { l mid 1; } } return l; }写二分的时候有个小建议mid不要写成(l r) / 2而是写成l (r - l) / 2。虽然在这个题里lr不会溢出但这是从大型数组二分查找里带出来的好习惯反正也不费事。每次循环范围缩小一半所以单次查找的开销是O(log n)。3.3 完整可运行的二分版本代码把排序和二分组合起来完整代码如下#include stdio.h #include stdlib.h int cmp(const void *a, const void *b) { long long x *(const long long *)a; long long y *(const long long *)b; return (x y) - (x y); } int lower_bound(long long arr[], int n, long long key) { int l 0, r n; while (l r) { int mid l (r - l) / 2; if (arr[mid] key) { r mid; } else { l mid 1; } } return l; } int upper_bound(long long arr[], int n, long long key) { int l 0, r n; while (l r) { int mid l (r - l) / 2; if (arr[mid] key) { r mid; } else { l mid 1; } } return l; } int main() { int n; long long c; long long a[100005]; long long ans 0; scanf(%d %lld, n, c); for (int i 0; i n; i) { scanf(%lld, a[i]); } qsort(a, n, sizeof(long long), cmp); for (int i 0; i n; i) { long long target a[i] c; int left lower_bound(a, n, target); int right upper_bound(a, n, target); if (c 0) { // 排除当前元素自身 ans (right - left) - 1; } else { ans right - left; } } printf(%lld\n, ans); return 0; }枚举数组里的每一个数作为A然后去数组里找B A - C。等等这里其实我写的target a[i] c是找B因为A - B C所以B A - C也就是a[i] - C。我代码里为什么要用a[i] c前面说了等价写法是 A B C所以枚举B时找B C。这里我枚举的其实是B找的是A。命名上要注意循环里每个a[i]当作Btargeta[i]c是我们要找的A。这样枚举每一个B把对应A的个数累加就是答案。如果题目要求A和B是不同位置的两个数那么在C0时target恰好等于a[i]本身自己不能算一对所以要减1。代码里有个细节值得说明为什么循环里对每个i都累加而没有去重因为数组里每个元素代表一个不同的位置即使两个位置的数相等它们也是不同的B所以对应的A对数要分别计入答案。这样累加不会重复反而保证每个下标对都算了一次逻辑上刚好正确。4. 哈希表方案手写开放寻址也能打进O(n)4.1 哈希表结构怎么设计排序加二分已经足够应付大部分题目了但还有一种思路值得了解那就是用哈希表把查询从O(log n)降到平均O(1)整体时间复杂度达到O(n)。C语言本身没有现成的哈希表需要自己实现一个简单的版本。针对这个题只需要一个支持“插入一个数”和“查询某个数出现次数”的哈希表。最常见的实现是开放寻址法也就是用一个结构体数组表示哈希桶每个桶记录键值和该键值的出现次数。如果哈希冲突了就往后线性探测找到空位或者相同键值的桶。示例结构体如下#define HASH_SIZE 2000003 typedef struct { long long key; int count; int used; } HashSlot; HashSlot hashTable[HASH_SIZE];used字段用来标记这个桶是否已经被占用。插入前要通过哈希函数计算下标这里哈希函数用取模即可注意C语言的负数取模结果还是负数所以要先加模数再取模int hashKey(long long key) { return (int)((key % HASH_SIZE HASH_SIZE) % HASH_SIZE); }4.2 哈希方案完整代码与复杂度分析完整代码如下#include stdio.h #define HASH_SIZE 2000003 typedef struct { long long key; int count; int used; } HashSlot; HashSlot hashTable[HASH_SIZE]; int hashKey(long long key) { return (int)((key % HASH_SIZE HASH_SIZE) % HASH_SIZE); } void insertKey(long long key) { int idx hashKey(key); while (hashTable[idx].used) { if (hashTable[idx].key key) { hashTable[idx].count; return; } idx (idx 1) % HASH_SIZE; } hashTable[idx].used 1; hashTable[idx].key key; hashTable[idx].count 1; } int queryKey(long long key) { int idx hashKey(key); while (hashTable[idx].used) { if (hashTable[idx].key key) { return hashTable[idx].count; } idx (idx 1) % HASH_SIZE; } return 0; } int main() { int n; long long c; long long a[100005]; long long ans 0; scanf(%d %lld, n, c); for (int i 0; i n; i) { scanf(%lld, a[i]); insertKey(a[i]); } for (int i 0; i n; i) { long long target a[i] c; int cnt queryKey(target); if (c 0) { cnt--; } ans cnt; } printf(%lld\n, ans); return 0; }哈希表的思路是把所有数插入表中记录每个值出现的次数。然后再次遍历数组把每个元素当作B在哈希表里查询A B C的出现次数累加到答案。时间复杂度平均是O(n)因为每次插入和查询都是常数时间。但哈希表有两个代价一是需要预开足够大的桶数组内存开销比排序方案大二是冲突过多时性能会退化虽然这里取模运算配合线性探测在随机数据下表现良好但刻意构造的数据可能会让线性探测变慢。这个方案的好处是思路直观而且不依赖排序适合那些“数组本身很大但值域分散”的场景。缺点也很明显需要手工维护结构体写起来比qsort加二分麻烦而且容易在hashKey函数上踩负数取模的坑。5. 真正实战中的三个坑溢出、C0 与排序比较函数5.1 坑一int 在 ac 面前不够用很多题目里数组元素的范围最大到10^9甚至2^31-1而C也可能到10^9。如果你用int存a[i]再用int去计算a[i] c结果可能会超过int的上限发生无符号溢出或者截断导致二分查找的target出错最终答案莫名少了或多了一大堆。解决办法很简单数组和target一律声明为long long。数据范围是10^9时int勉强能存单个元素但存不下相加后的结果。我在PTA上见过不少同学代码思路全对就是int导致大数测试点WA改long long之后直接AC。这个教训值得记下来在涉及加法和比较的算法题里不要吝啬用long long。5.2 坑二C0 时每个元素会把自己算进去如果C等于0那么条件变成A - B 0也就是A B。这时候每一个数对同一个位置的两个相同元素也满足条件。如果题目要求的是“两个不同位置的数”那每个元素自己和自己组成的一对就要被排除掉。这个坑非常隐蔽因为样例数据通常不包含C0的情况。你在排序加二分的版本里循环枚举B查找A B C B时二分找到的范围既包括其他等于B的元素也包括B自己在数组里的那次出现。处理办法就是当C 0时对每个元素的查询结果都减1。哈希表版本同理queryKey返回的是等于target的全部元素个数其中也包括当前遍历到的这个元素本身所以也要减1。这里还有个更严格的变体如果题目要求i j也就是统计有序下标对的数量那情况会更复杂一些。大部分OJ上的“A-B数对”统计的是无序下标对恰好和上面的处理方式对应。如果你读到的题面明确写了“i j”那么排序加二分的写法就需要改成只统计位于当前元素之后的部分或者用“总数减半”的思路去处理。我建议做题前先把题面里“数对”的定义读清楚这个决定直接影响答案。5.3 坑三qsort 比较函数写成减法会出大问题这个坑前面提过一次但因为它太常见了我还是要单独拉出来强调。很多人写qsort的比较函数时图省事写成了int cmp(const void *a, const void *b) { return *(long long *)a - *(long long *)b; }乍一看没问题但函数的返回值是int如果两个long long的差值超过int范围减法结果会被截断产生完全错误的排序。比如两个数分别是2000000000和-2000000000差值远超过int上限截断后可能变成一个正数或负数排序就乱了。正确写法是不做减法而是用比较结果来生成返回值int cmp(const void *a, const void *b) { long long x *(const long long *)a; long long y *(const long long *)b; return (x y) - (x y); }这个写法无论数据类型多大都很安全而且语义清晰x大于y返回1x小于y返回-1相等返回0。6. 两数之差类题目的通用套路与变形6.1 统一套路枚举一个数查询另一个数做完这一题你会发现它背后其实是一类题目的通用模型给定一个数组和一个目标关系求满足关系的数对个数。核心套路就是“枚举一个数用高效的数据结构查询另一个数”。这里的“另一个数”可以是xC、x-C、C-x也可以是“和小于C的最远位置”这种更复杂的关系。在C语言里这个“高效查询”通常有三种落地方式排序加二分、排序加双指针、哈希表。三者适用的场景略有不同。排序加二分最容易写也是我推荐大部分初学者掌握的双指针适合处理“求小于某个阈值的数对数量”这类问题哈希表则在值域分散、需要频繁精确匹配时更占优势。方案时间复杂度额外内存写码难度适用场景双重循环O(n²)无最低小数据验证排序二分O(n log n)无中绝大多数题目结构体哈希表平均O(n)较高较高需要O(n)复杂度的场景6.2 变体题从 A-BC 到 ABC、差值区间、最近差值理解了A-BC之后很多变体题就是换汤不换药。比如统计ABC的数对数量。这时还是枚举B然后去数组里找C - B这个值。如果数组有序也可以用双指针从两端往中间扫比二分更快能优化到O(n)。双指针的核心逻辑是左指针指向较小值右指针指向较大值当两数之和等于C时根据是否允许重复值来决定怎么移动指针。再比如统计两数差值的绝对值不超过K的对数。排序之后可以枚举每一个数作为右端点然后用二分找到第一个差值大于K的左端点两者之间的元素个数就是贡献。这种“枚举右端点、二分左端点”的思路在很多区间计数问题里都能见到。还有一类变形是求两个数之和或差最接近某个目标值。方法依然排序然后双指针逼近目标每次根据当前和或差的大小关系移动指针。你会发现只要把“A-BC”的数学式理解透这些题目背后的代码骨架几乎一样。6.3 给我的几点工程启发回到C语言本身这道题给我最大的启发是C语言的标准库虽然简单但组合起来非常强大。qsort负责排序二分查找自己写十几行哈希表也就几十行三个工具配合起来就能解决一大类查询统计问题。很多初学者容易陷入“到处找现成库函数”的思维其实在C语言里手写这些基础数据结构本身就是学习的一部分。你会更清楚二分查找的边界条件更明白哈希冲突怎么处理而不是只会调用别人的API。另一个启发是写算法题之前一定要把数据范围看明白。范围决定思路思路决定代码。n1000时可以暴力n100000时就必须排序或者哈希n1000000时连排序都要想想用什么排序。这个问题里数据范围直接决定了你能不能用long long、要不要处理负数、要不要考虑溢出提前想清楚可以省下大量调试时间。最后分享一个我自己的小习惯每次写完一版解法我都会保留暴力版本再写优化版本然后随机生成一堆小数据去对拍。暴力版本虽然慢但正确性容易保证用它当“裁判”优化版本的结果和它不一致就立刻知道了。这个对拍习惯帮我抓出了不止一次C0、负数溢出这类隐蔽问题比对着评测结果猜答案高效得多。如果你也经常被隐藏测试点折磨建议试试这个方法。
开局先说实话“A-B数对”这道题本身不难题意一句话就能说清但它是我见过的“看起来简单翻车率却极高”的一类C语言入门算法题。很多人在PTA、洛谷或者学校OJ上第一次遇到它顺手写个双重循环样例一跑发现结果对自信提交然后收获一个红色的超时。也有人优化了排序、二分、哈希都上了结果在C0的测试点翻车或者在负数的数据上莫名其妙的WA答案错误。这篇文章不打算只贴一份能过的代码而是把我从暴力解法一路走到排序二分、再走到手写哈希表的完整思路以及过程中踩过的坑全部摊开来讲一遍。适合正在学C语言、刚接触算法题的读者也适合那些代码能过但没想明白“为什么这么写”的同学。1. 题目到底在算什么东西从“数对”二字说起1.1 题意拆解A-BC 和 ABC 是一回事有一组数给定一个整数C问你一共有多少个数对(i, j)满足第i个数减第j个数等于C。用数学式表达就是A[i] - A[j] C这里说的“数对”指的是两个元素注意它不是指元素值相等就算一对而是指数组里不同位置的两个数。举例来说数组是 [2, 3, 5]C2那么满足条件的有 3 - 2 2 和 5 - 3 2 这两对。如果你把式子移项A[i] - A[j] C 就等价于 A[i] A[j] C也等价于 A[j] A[i] - C。也就是说只要枚举其中一个数找另一个数就行。很多同学在做这一题的时候脑袋里想的是“差为C的两个数”但写代码时却把简单的数学表达式搞混了。我见过有人写if (a[i] - a[j] C) 结果用了双重循环也有人把条件写成 a[i] C a[j]方向搞反样例直接不对。这里最好一开始就明确枚举谁、找谁。1.2 最容易理解错的两个细节重复值和负数第一个细节是重复值。数组里有多个相同的数时它们对应的下标不同所以它们参与组成的数对都要算进去。比如数组 [1, 1, 3]C2那么 3 - 1 2 算两对因为有两个1每个1都和一个3组成一个合法数对。有些同学排序后给数组去重结果答案直接少了一半这是非常典型的错法。第二个细节是负数。C是题目给定的常数它可能是正数、负数或者0。很多人默认数组元素都是非负整数直接拿哈希或者排序的思路写结果遇到负数数据就挂了。比如数组 [-2, 0, 2]C-2满足 A - B -2 的数对有-2 - 0 -20 - 2 -2共两对。如果你做的是“枚举一个数在数组里二分查找另一个数”这条路对负数没有任何问题只要比较函数写得正确就行。把这两个细节记在脑子里再看下面的优化过程你就知道哪些坑是必须绕开的。2. 第一版方案暴力双重循环为什么必然会超时2.1 暴力代码谁都能三分钟写出来的版本先看看最简单的实现代码核心就一个双重循环。假如数组有n个元素#include stdio.h int main() { int n, c; int a[100005]; long long ans 0; scanf(%d %d, n, c); for (int i 0; i n; i) { scanf(%d, a[i]); } for (int i 0; i n; i) { for (int j 0; j n; j) { if (a[i] - a[j] c) { ans; } } } printf(%lld\n, ans); return 0; }这段代码逻辑完全正确尤其适合拿来对拍、验证后面优化版本的正确性。它的时间复杂度是O(n²)因为两层循环把每一对元素都检查了一遍。2.2 实测一把N10^5 时双重循环到底跑了多久我当年第一次交这个版本是在数据规模n最大10^5的OJ上。当时想着C语言跑得快双重循环应该没问题结果超时到怀疑人生。我们来估算一下n100000时双重循环总共要执行大约10^10次减法运算和比较运算。即使你的机器一秒能跑10^8次简单运算10^10这个量级也至少要几十秒OJ普遍限时1秒这显然过不去。还有一个容易被忽略的点双重循环里如果还带着scanf和printf那IO开销会进一步拖慢程序。所以暴力版本唯一的用途就是“验证思路”不是“提交答案”。3. 排序加二分C语言选手最顺手的优化路径3.1 qsort 排序细节比较函数别用减法既然双重循环太慢那就得换思路。我们要找的是“一个数等于另一个数加C”的配对关系如果能提前把数组排好序那么对于每一个数x只需要在有序数组里查找xC存不存在、存在几个。整体复杂度可以降到O(n log n)这是排序加二分的思想。C语言排序首选qsort。但这里有个大坑很多教程教人写比较函数时直接返回两个数的差比如int cmp(const void *a, const void *b) { return *(int *)a - *(int *)b; }在元素是int且差值不大的情况下这段代码可以用。但如果差值超出int范围或者以后你把数组改成long long减法结果就会溢出导致排序出错。正确的写法是改写为“大于返回1小于返回-1等于返回0”的形式int cmp(const void *a, const void *b) { long long x *(const long long *)a; long long y *(const long long *)b; return (x y) - (x y); }这种写法不会溢出而且对负数也天然正确。我建议不管题目数据范围多大养成这个习惯能省掉很多莫名其妙的WA。3.2 手写 lower_bound 与 upper_bound而不是搜标准库C语言不像C有现成的lower_bound和upper_bound函数可以用所以需要自己手写二分查找。这里要查的是“xC这个值在有序数组里出现的次数”更准确地说要找到第一个大于等于xC的位置和第一个大于xC的位置两个位置的下标差就是xC的出现次数。手写二分的关键是边界条件。我常用的写法是左闭右开区间也就是用两个变量l和r表示[l, r)这个查找范围。查找lower_bound的代码是这样int lower_bound(long long arr[], int n, long long key) { int l 0, r n; while (l r) { int mid l (r - l) / 2; if (arr[mid] key) { r mid; } else { l mid 1; } } return l; }upper_bound的代码只是把arr[mid] key改成arr[mid] keyint upper_bound(long long arr[], int n, long long key) { int l 0, r n; while (l r) { int mid l (r - l) / 2; if (arr[mid] key) { r mid; } else { l mid 1; } } return l; }写二分的时候有个小建议mid不要写成(l r) / 2而是写成l (r - l) / 2。虽然在这个题里lr不会溢出但这是从大型数组二分查找里带出来的好习惯反正也不费事。每次循环范围缩小一半所以单次查找的开销是O(log n)。3.3 完整可运行的二分版本代码把排序和二分组合起来完整代码如下#include stdio.h #include stdlib.h int cmp(const void *a, const void *b) { long long x *(const long long *)a; long long y *(const long long *)b; return (x y) - (x y); } int lower_bound(long long arr[], int n, long long key) { int l 0, r n; while (l r) { int mid l (r - l) / 2; if (arr[mid] key) { r mid; } else { l mid 1; } } return l; } int upper_bound(long long arr[], int n, long long key) { int l 0, r n; while (l r) { int mid l (r - l) / 2; if (arr[mid] key) { r mid; } else { l mid 1; } } return l; } int main() { int n; long long c; long long a[100005]; long long ans 0; scanf(%d %lld, n, c); for (int i 0; i n; i) { scanf(%lld, a[i]); } qsort(a, n, sizeof(long long), cmp); for (int i 0; i n; i) { long long target a[i] c; int left lower_bound(a, n, target); int right upper_bound(a, n, target); if (c 0) { // 排除当前元素自身 ans (right - left) - 1; } else { ans right - left; } } printf(%lld\n, ans); return 0; }枚举数组里的每一个数作为A然后去数组里找B A - C。等等这里其实我写的target a[i] c是找B因为A - B C所以B A - C也就是a[i] - C。我代码里为什么要用a[i] c前面说了等价写法是 A B C所以枚举B时找B C。这里我枚举的其实是B找的是A。命名上要注意循环里每个a[i]当作Btargeta[i]c是我们要找的A。这样枚举每一个B把对应A的个数累加就是答案。如果题目要求A和B是不同位置的两个数那么在C0时target恰好等于a[i]本身自己不能算一对所以要减1。代码里有个细节值得说明为什么循环里对每个i都累加而没有去重因为数组里每个元素代表一个不同的位置即使两个位置的数相等它们也是不同的B所以对应的A对数要分别计入答案。这样累加不会重复反而保证每个下标对都算了一次逻辑上刚好正确。4. 哈希表方案手写开放寻址也能打进O(n)4.1 哈希表结构怎么设计排序加二分已经足够应付大部分题目了但还有一种思路值得了解那就是用哈希表把查询从O(log n)降到平均O(1)整体时间复杂度达到O(n)。C语言本身没有现成的哈希表需要自己实现一个简单的版本。针对这个题只需要一个支持“插入一个数”和“查询某个数出现次数”的哈希表。最常见的实现是开放寻址法也就是用一个结构体数组表示哈希桶每个桶记录键值和该键值的出现次数。如果哈希冲突了就往后线性探测找到空位或者相同键值的桶。示例结构体如下#define HASH_SIZE 2000003 typedef struct { long long key; int count; int used; } HashSlot; HashSlot hashTable[HASH_SIZE];used字段用来标记这个桶是否已经被占用。插入前要通过哈希函数计算下标这里哈希函数用取模即可注意C语言的负数取模结果还是负数所以要先加模数再取模int hashKey(long long key) { return (int)((key % HASH_SIZE HASH_SIZE) % HASH_SIZE); }4.2 哈希方案完整代码与复杂度分析完整代码如下#include stdio.h #define HASH_SIZE 2000003 typedef struct { long long key; int count; int used; } HashSlot; HashSlot hashTable[HASH_SIZE]; int hashKey(long long key) { return (int)((key % HASH_SIZE HASH_SIZE) % HASH_SIZE); } void insertKey(long long key) { int idx hashKey(key); while (hashTable[idx].used) { if (hashTable[idx].key key) { hashTable[idx].count; return; } idx (idx 1) % HASH_SIZE; } hashTable[idx].used 1; hashTable[idx].key key; hashTable[idx].count 1; } int queryKey(long long key) { int idx hashKey(key); while (hashTable[idx].used) { if (hashTable[idx].key key) { return hashTable[idx].count; } idx (idx 1) % HASH_SIZE; } return 0; } int main() { int n; long long c; long long a[100005]; long long ans 0; scanf(%d %lld, n, c); for (int i 0; i n; i) { scanf(%lld, a[i]); insertKey(a[i]); } for (int i 0; i n; i) { long long target a[i] c; int cnt queryKey(target); if (c 0) { cnt--; } ans cnt; } printf(%lld\n, ans); return 0; }哈希表的思路是把所有数插入表中记录每个值出现的次数。然后再次遍历数组把每个元素当作B在哈希表里查询A B C的出现次数累加到答案。时间复杂度平均是O(n)因为每次插入和查询都是常数时间。但哈希表有两个代价一是需要预开足够大的桶数组内存开销比排序方案大二是冲突过多时性能会退化虽然这里取模运算配合线性探测在随机数据下表现良好但刻意构造的数据可能会让线性探测变慢。这个方案的好处是思路直观而且不依赖排序适合那些“数组本身很大但值域分散”的场景。缺点也很明显需要手工维护结构体写起来比qsort加二分麻烦而且容易在hashKey函数上踩负数取模的坑。5. 真正实战中的三个坑溢出、C0 与排序比较函数5.1 坑一int 在 ac 面前不够用很多题目里数组元素的范围最大到10^9甚至2^31-1而C也可能到10^9。如果你用int存a[i]再用int去计算a[i] c结果可能会超过int的上限发生无符号溢出或者截断导致二分查找的target出错最终答案莫名少了或多了一大堆。解决办法很简单数组和target一律声明为long long。数据范围是10^9时int勉强能存单个元素但存不下相加后的结果。我在PTA上见过不少同学代码思路全对就是int导致大数测试点WA改long long之后直接AC。这个教训值得记下来在涉及加法和比较的算法题里不要吝啬用long long。5.2 坑二C0 时每个元素会把自己算进去如果C等于0那么条件变成A - B 0也就是A B。这时候每一个数对同一个位置的两个相同元素也满足条件。如果题目要求的是“两个不同位置的数”那每个元素自己和自己组成的一对就要被排除掉。这个坑非常隐蔽因为样例数据通常不包含C0的情况。你在排序加二分的版本里循环枚举B查找A B C B时二分找到的范围既包括其他等于B的元素也包括B自己在数组里的那次出现。处理办法就是当C 0时对每个元素的查询结果都减1。哈希表版本同理queryKey返回的是等于target的全部元素个数其中也包括当前遍历到的这个元素本身所以也要减1。这里还有个更严格的变体如果题目要求i j也就是统计有序下标对的数量那情况会更复杂一些。大部分OJ上的“A-B数对”统计的是无序下标对恰好和上面的处理方式对应。如果你读到的题面明确写了“i j”那么排序加二分的写法就需要改成只统计位于当前元素之后的部分或者用“总数减半”的思路去处理。我建议做题前先把题面里“数对”的定义读清楚这个决定直接影响答案。5.3 坑三qsort 比较函数写成减法会出大问题这个坑前面提过一次但因为它太常见了我还是要单独拉出来强调。很多人写qsort的比较函数时图省事写成了int cmp(const void *a, const void *b) { return *(long long *)a - *(long long *)b; }乍一看没问题但函数的返回值是int如果两个long long的差值超过int范围减法结果会被截断产生完全错误的排序。比如两个数分别是2000000000和-2000000000差值远超过int上限截断后可能变成一个正数或负数排序就乱了。正确写法是不做减法而是用比较结果来生成返回值int cmp(const void *a, const void *b) { long long x *(const long long *)a; long long y *(const long long *)b; return (x y) - (x y); }这个写法无论数据类型多大都很安全而且语义清晰x大于y返回1x小于y返回-1相等返回0。6. 两数之差类题目的通用套路与变形6.1 统一套路枚举一个数查询另一个数做完这一题你会发现它背后其实是一类题目的通用模型给定一个数组和一个目标关系求满足关系的数对个数。核心套路就是“枚举一个数用高效的数据结构查询另一个数”。这里的“另一个数”可以是xC、x-C、C-x也可以是“和小于C的最远位置”这种更复杂的关系。在C语言里这个“高效查询”通常有三种落地方式排序加二分、排序加双指针、哈希表。三者适用的场景略有不同。排序加二分最容易写也是我推荐大部分初学者掌握的双指针适合处理“求小于某个阈值的数对数量”这类问题哈希表则在值域分散、需要频繁精确匹配时更占优势。方案时间复杂度额外内存写码难度适用场景双重循环O(n²)无最低小数据验证排序二分O(n log n)无中绝大多数题目结构体哈希表平均O(n)较高较高需要O(n)复杂度的场景6.2 变体题从 A-BC 到 ABC、差值区间、最近差值理解了A-BC之后很多变体题就是换汤不换药。比如统计ABC的数对数量。这时还是枚举B然后去数组里找C - B这个值。如果数组有序也可以用双指针从两端往中间扫比二分更快能优化到O(n)。双指针的核心逻辑是左指针指向较小值右指针指向较大值当两数之和等于C时根据是否允许重复值来决定怎么移动指针。再比如统计两数差值的绝对值不超过K的对数。排序之后可以枚举每一个数作为右端点然后用二分找到第一个差值大于K的左端点两者之间的元素个数就是贡献。这种“枚举右端点、二分左端点”的思路在很多区间计数问题里都能见到。还有一类变形是求两个数之和或差最接近某个目标值。方法依然排序然后双指针逼近目标每次根据当前和或差的大小关系移动指针。你会发现只要把“A-BC”的数学式理解透这些题目背后的代码骨架几乎一样。6.3 给我的几点工程启发回到C语言本身这道题给我最大的启发是C语言的标准库虽然简单但组合起来非常强大。qsort负责排序二分查找自己写十几行哈希表也就几十行三个工具配合起来就能解决一大类查询统计问题。很多初学者容易陷入“到处找现成库函数”的思维其实在C语言里手写这些基础数据结构本身就是学习的一部分。你会更清楚二分查找的边界条件更明白哈希冲突怎么处理而不是只会调用别人的API。另一个启发是写算法题之前一定要把数据范围看明白。范围决定思路思路决定代码。n1000时可以暴力n100000时就必须排序或者哈希n1000000时连排序都要想想用什么排序。这个问题里数据范围直接决定了你能不能用long long、要不要处理负数、要不要考虑溢出提前想清楚可以省下大量调试时间。最后分享一个我自己的小习惯每次写完一版解法我都会保留暴力版本再写优化版本然后随机生成一堆小数据去对拍。暴力版本虽然慢但正确性容易保证用它当“裁判”优化版本的结果和它不一致就立刻知道了。这个对拍习惯帮我抓出了不止一次C0、负数溢出这类隐蔽问题比对着评测结果猜答案高效得多。如果你也经常被隐藏测试点折磨建议试试这个方法。
