C语言A-B数对高效解法：排序二分与哈希计数

我刚刷到一个很经典的问题标题写着“C语言之A-B数对”。如果只看名字可能以为又是那种教科书上的数学应用题实际上它是算法刷题里特别常见的计数类题目也是笔试面试里用来考察你C语言基本功和算法思维的好材料。很多人在刚开始接触这道题的时候第一反应都是双层for循环暴力枚举结果一提交就超时。真正能把这道题做好的人往往是对排序、二分、哈希表、数组偏移这些C语言基础操作有扎实理解的人。这篇文章我打算把A-B数对这道题从题目拆解讲到底层实现再说到完整代码演进和调试经验。不管你是刚学C语言、在准备计算机二级还是想给单片机开发打基础这篇文章都能让你看懂核心思路并且拿到可以直接复制的代码。同时我也会结合近期网上大家比较关心的C语言问题比如指针、内存管理、qsort用法、输入输出格式等把这道题背后真正值得学的C语言细节一并讲透。1. 题目到底在问什么先读懂A-B数对的真实需求1.1 从文字描述到数学模型的转化先明确一下题目的经典描述。给你一个包含n个整数的数组再给一个常数C要求统计一共有多少个数对(i, j)满足a[i] - a[j] C。这里需要注意几点数对里的i和j是数组下标强调的是位置不是单纯的值。有的题目说i和j可以相同有的说不能相同以实际题目描述为准。数组里的元素可能重复出现重复值时每个位置都要分别计数。数据范围通常很大比如n可以达到10^5甚至更大值域也可能是负数到正数的大范围。把文字变成数学表达式就是统计满足 a[j] a[i] - C 的所有(i, j)组合个数。这个变形是整个题目的灵魂它把减法问题转换成了“查找另一个数是否存在、存在几个”的查找问题。很多同学上来就写两层循环就是没有意识到这个变形才是最佳解法的起点。提示拿到算法题第一步永远是先把已知条件改写成等价形式。a[i] - a[j] C等价于 a[j] a[i] - C也等价于 a[i] a[j] C。选哪个方向看题目怎么方便。1.2 为什么不能看到减法就马上暴力枚举最朴素的想法两个for循环外层枚举a[i]内层枚举a[j]判断差值是否等于C。这个做法从逻辑上来说完全正确但它的时间复杂度是O(n²)。当n10^5时10^5的平方等于10^10次运算哪怕你的电脑1秒能跑2亿次简单操作也需要50秒以上。在绝大多数OJ系统限时1秒的规则下这个方案必然超时。所以这道题真正的考察点不是你能不能把它算出来而是你能不能通过预处理、排序或哈希表把复杂度降下来。这种把O(n²)降到O(n log n)或O(n)的思维才是算法学习中最值钱的能力。很多新手卡在这一步就放弃了其实只要把“查找”这个动作单独拎出来想思路就清晰了。1.3 值域、下标和位置的三个坑每一次做这道题我都会提醒自己注意三个细节。第一个坑是值域C和数组元素都可能很大做减法的时候要注意int范围别直接溢出第二个坑是下标计数如果你用哈希桶来统计元素出现次数而元素有负数那么桶下标就不能直接用a[i]需要加一个偏移量第三个坑是数对计数口径有的题是看位置对有的题是看值对如果数组里有多个相同值位置对和值对的计数结果会差很多。踩过这几个坑之后我深刻体会到C语言的题看起来是考语法实际上考的是你有没有把问题边界想清楚。边界清楚了代码自然好写边界模糊写出来的代码看似正确一提交就错。2. 三种主流的解法思路对比2.1 暴力枚举法拿来验证思路不推荐提交先用暴力法验证思路是有价值的。代码大概是两层循环int count 0; for (int i 0; i n; i) { for (int j 0; j n; j) { if (a[i] - a[j] C) { count; } } }如果你只是小规模测试比如n100这段代码完全能跑。而且它逻辑直观能帮你确认题目描述里的数对口径到底是怎么算的。我以前做新题时都会先用暴力法跑一遍小样例验证了我对题意的理解再上高效算法这个习惯帮我避免过很多次因题意理解偏差而导致的错误。但要注意暴力法里如果允许i和j相同那么对于每个iji时差值恒为0这会在C0时产生干扰。很多题明确要求i≠j那就需要在循环里加一个if (i j) continue;。先在小数据里把这个逻辑测试清楚后面优化版本才不会写错。2.2 排序后二分查找最稳的C语言主流方案既然暴力查找慢那我们就提前把数组排好序然后用二分查找快速定位。思路是枚举每个a[i]计算target a[i] - C然后在有序数组里查找target出现的次数。由于排序后相同元素会聚在一起我们可以用二分找到target的左边界和右边界两个下标相减加1就是出现次数把每个i对应的次数累加就是答案。用C语言实现时排序用标准库的qsort二分可以用手写的lower_bound和upper_bound。整个过程的时间复杂度是O(n log n)空间复杂度O(1)。这个方案不依赖值的范围负数正数都能处理而且代码逻辑非常清晰是考试和面试中最推荐的方案。我最喜欢这个方案的原因是它只用到了数组和指针不涉及复杂的哈希表设计。你只要把qsort的比较函数写对把二分的边界想清楚基本就能拿到满分。对C语言初学者来说这也是练习指针和qsort标准库函数最好的载体。2.3 哈希计数法时间复杂度最优但要求高如果能保证数组元素的值域不太大哈希计数法可以做到O(n)复杂度。基本思想是统计每个值出现的次数然后再次遍历数组对每个a[i]看a[i] - C这个值在哈希表里出现了多少次累加即可。C语言没有内置的哈希表所以我们通常用一个大数组来模拟把值直接映射成数组下标。这里有个非常关键的操作如果数组里有负数那么下标也会是负数C语言数组不允许负下标所以需要给每个值加一个统一的偏移量比如把所有值加100000保证映射后的下标从0开始。偏移量的大小取决于值域范围。还有一种更进阶的做法是手写链表式哈希表或者用开放寻址法处理冲突。但说实话在大多数题目场景下数组模拟已经够用。哈希法唯一的风险是空间浪费如果值域跨度很大但元素很少开一个超大的数组就很不划算。这时候可以考虑先做离散化把所有出现过的不同值映射成连续的编号再用数组统计。2.4 三种方案对比速查表方案时间复杂度空间复杂度编码难度适用场景暴力枚举O(n²)O(1)极低小数据、验证题意排序二分O(n log n)O(1)中等n较大值域无限制哈希计数O(n)O(值域或去重数)较高值域可控追求最快如果你问我个人怎么选我一般这样判断先看题目数据范围如果n超过10^5暴力法直接放弃如果值域是类似[-10^5, 10^5]这种可接受范围哈希法最快如果值域很离谱比如-2^31到2^31老老实实排序加二分。实际工作中这个思路同样适用处理数据时先评估数据规模和数据分布再选算法不要一上来就炫技。3. C语言实现里的核心细节与原理拆解3.1 用qsort排序时比较函数到底该怎么写C语言初学者最容易在qsort上翻车。qsort的函数指针格式是固定的比较函数必须返回int接收两个const void参数。我们在内部转成int再解引用然后返回差值。代码如下int cmp(const void *a, const void *b) { return *(int *)a - *(int *)b; } qsort(a, n, sizeof(int), cmp);这里有个隐蔽的坑如果两个数都是很大的正数比如2000000000和-2000000000两者相减可能溢出int导致比较结果错误。更安全的写法是用逻辑判断int cmp(const void *a, const void *b) { int x *(int *)a; int y *(int *)b; if (x y) return -1; if (x y) return 1; return 0; }第二种写法多写几行但避免了溢出问题。这个细节在C语言编程中非常典型直觉上的“返回a-b”在大多数情况下没问题一旦数据规模上去就会出bug。好的程序员会在这种地方提前设防。3.2 手写二分查找左边界与右边界的艺术二分查找的核心不是背模板而是理解循环不变量。我习惯这样写在有序数组中查找target第一次出现的位置如果不存在返回第一个大于target的位置查找最后一次出现的位置返回最后一个小于等于target的位置。两个函数配合就能统计出现次数。int lower_bound(int *a, int n, int target) { int l 0, r n; while (l r) { int mid l (r - l) / 2; if (a[mid] target) l mid 1; else r mid; } return l; } int upper_bound(int *a, int n, int target) { int l 0, r n; while (l r) { int mid l (r - l) / 2; if (a[mid] target) l mid 1; else r mid; } return l; }之后统计数量就是upper_bound(...) - lower_bound(...)。别看代码短里面的细节很值得琢磨r n表示搜索区间是左闭右开mid l (r - l) / 2是为了防止l和r很大时直接(lr)/2溢出。这些写法都是从工程实践中沉淀下来的背下来能少踩很多坑。3.3 哈希法里的负数偏移与计数精度如果数组里有负数比如数据范围是[-50000, 50000]那么元素值加50000之后范围就是[0, 100000]用长度为100001的数组就能放下。映射函数就是idx x OFFSET。注意这里OFFSET必须大于等于绝对值最小的负数如果题目给的是闭区间建议把OFFSET设成绝对值下界数组长度设为上界加下界加1。当C本身也是负数时target a[i] - C反而会变大这没问题只要判断target是否在映射后的下标范围内即可。但如果你在做映射时没判断边界访问越界下标会导致段错误。我做过一个题数据范围给得很大我偷懒把数组开小了结果跑起来直接崩调试了半天。注意哈希数组下标判断要放在访问之前养成习惯先判断target是否在值域内再查表千万不能不管边界直接cnt[target OFFSET]。3.4 用long long承接答案避免计数溢出这道题最终的答案规模可能很大。举个例子n10^5数组里全是同一个数C0条件对所有i,j都成立答案就是n*(n-1)如果不允许ji大概是10^10这已经超出int的21亿上限了。因此计数器必须用long long。输出时用printf(%lld\n, ans)。这一点特别容易被忽略因为小数据测试时int完全够用只有跑大数据才会暴露。我的建议是凡是计数类题目答案累加变量一律开long long哪怕最终答案很小也没关系提前设防总比事后调试划算。这跟上面的比较函数防溢出逻辑是一脉相承的。4. 完整代码演进从暴力到二分到哈希的实操记录4.1 第一版暴力验证题意验证阶段我直接写最笨的代码目标是跑通样例并确认题目里“数对”的定义。下面是完整代码#include stdio.h int main() { int n, C; scanf(%d %d, n, C); int a[1005]; for (int i 0; i n; i) scanf(%d, a[i]); long long ans 0; for (int i 0; i n; i) { for (int j 0; j n; j) { if (i ! j a[i] - a[j] C) { ans; } } } printf(%lld\n, ans); return 0; }这里有个小细节我暂时把数组开成1005是为了方便小数据测试。如果你把数组初始化为1005却输入n2000就会越界。测试时数组大小一定要根据实际输入调整不要抱有侥幸心理。你可以输入这样的样例来验证n5, C2, 数组[1,2,3,4,5]满足a[i]-a[j]2的数对有(3,1)、(4,2)、(5,3)答案是3。跑出来是3说明题意理解没问题。4.2 第二版排序加二分正式提交版确认题意后果断换成排序加二分#include stdio.h #include stdlib.h int cmp(const void *a, const void *b) { int x *(int *)a; int y *(int *)b; if (x y) return -1; if (x y) return 1; return 0; } int lower_bound(int *a, int n, int target) { int l 0, r n; while (l r) { int mid l (r - l) / 2; if (a[mid] target) l mid 1; else r mid; } return l; } int upper_bound(int *a, int n, int target) { int l 0, r n; while (l r) { int mid l (r - l) / 2; if (a[mid] target) l mid 1; else r mid; } return l; } int main() { int n, C; scanf(%d %d, n, C); int *a (int *)malloc(n * sizeof(int)); for (int i 0; i n; i) scanf(%d, a[i]); qsort(a, n, sizeof(int), cmp); long long ans 0; for (int i 0; i n; i) { int target a[i] - C; int l lower_bound(a, n, target); int r upper_bound(a, n, target); ans r - l; } printf(%lld\n, ans); return 0; }这里我用malloc动态分配数组是考虑n的数据范围不固定。如果直接用int a[100005]也可以但malloc的做法更加体现内存管理意识也方便n特别大的时候使用。如果你是在VS Code里配置好了C语言环境这套代码直接编译运行没问题。注意这段代码默认允许ji。当C0时targeta[i]lower_bound找到a[i]的位置upper_bound找到它之后的位置减出来的数量包含了自己。如果题目要求数对(i,j)中i和j不能是同一个位置需要在结果里减去n因为每个i都多算了一次自身。如果数组里有重复元素这种“只减n”的做法依然成立因为每个位置恰好只多算自己一次。验证一下n5, C2, [1,2,3,4,5]排序后二分查targeta[i]-2依次得到3、4、5的计数总数是3和暴力法结果一致。4.3 第三版值域可控时的哈希计数法当题目明确了值域比如数值都在[-50000, 50000]内我会用哈希计数法拿到O(n)的版本#include stdio.h #include string.h #define OFFSET 50000 #define MAXN 100005 int cnt[MAXN]; int main() { int n, C; scanf(%d %d, n, C); int a[MAXN]; for (int i 0; i n; i) { scanf(%d, a[i]); cnt[a[i] OFFSET]; } long long ans 0; for (int i 0; i n; i) { int target a[i] - C; if (target OFFSET 0 target OFFSET MAXN) { ans cnt[target OFFSET]; } } printf(%lld\n, ans); return 0; }这段代码非常简短核心就是把每个值出现的次数提前统计好然后一次遍历查表。别忘了C0时cnt[a[i] OFFSET]包含了自身需要根据题目要求决定是否减n。我建议把这个“自身元素处理”逻辑单独提取出来写注释说明这样代码阅读性更好。比如样例[1,2,3,4,5], C2统计后1出现1次2出现1次...查表时i0的target-1没出现i2的target1出现1次i3的target2出现1次i4的target3出现1次累加得3。4.4 测试用例设计别只靠题目样例真正让我进步很快的习惯是自己设计边界测试用例。这道题我至少会测这几组n1时如果j不能等于i且C0答案应为0。所有元素相同的数组比如[5,5,5], C0如果j不能等于i答案应为6每个位置和其他两个位置各成一对方向。值域包含负数的数组比如[-3,-1,1,3], C2验证哈希法的偏移映射是否正常。大数极端场景比如n100000答案是否溢出int输出是否符合long long格式。我强烈建议你把这几个样例单独写进注释里以后复习时一目了然。很多新手提交错误后不知道怎么调试其实就是缺少“边界用例库”这个概念。把可能出错的边界提前想清楚你的代码质量会上一个台阶。5. 常见问题与排查技巧实录5.1 为什么我用了哈希法还是超时有一种情况是数组开得太大每次memset清零耗时高。比如值域是10^6每次测试都清空100万个int10组测试就是1000万次赋值速度会拖慢。更合理的方式是只重置用过的位置或者用时间戳数组代替memset用vis[id] ! stamp判断是否访问过。这个技巧在竞赛里常见工程上也可以借鉴避免对全量数据做无效清空。也有可能是你用了结构体加链表实现的哈希表每次查找都动态分配节点导致大量malloc调用。 malloc虽然方便但单次调用开销不小频繁调用在高频场景下会拖慢性能。数组模拟通常比链表哈希快一个量级这就是为什么我推荐优先数组模拟。5.2 答案偏大或偏小检查数对计数口径如果你的答案是预期的一倍左右多半是数对(i,j)和(j,i)都算进去了而题目只需要单向满足a[i]-a[j]C。如果你发现小样例对大样例错很可能是重复元素计数有误。统一口径最简单的方法是严格按照题目表达式来表达式里是a[i] - a[j] C就按它写不要自己改写成a[j] - a[i] C除非你确认题目允许对称计数。对于“是否包含自身”的问题我见过不少代码在哈希版本里直接ans cnt[target OFFSET]C0时就把自己算进去了。如果你发现C0时答案总比预期大n就可以确定是这个原因。5.3 提示段错误或下标越界优先查哈希偏移哈希法最容易踩的就是目标值超出了数组范围。题目值域是[-50000, 50000]但是C可能是负的target a[i] - C后可能达到100000以上超出数组长度。这类错误在本地跑小数据时常常不报错只有遇到极端值才崩溃。调试时可以加打印语句打印target的下标值一眼就能看出是否越界。提示凡是数组下标由计算得到的先判断范围再访问这是C语言内存安全的基本功。养成这个习惯段错误能少一半。5.4 qsort排序之后顺序乱了影响原来下标如果你在排序后还需要使用原来的下标比如题目要求同时输出原始位置那就不能直接排序原数组而是要排序一个结构体数组结构体里同时存值和原始下标。这里的比较函数也要改成比较结构体里的值字段。很多新手直接在原数组上排完序才发现下标信息丢了只能懊悔重写。我建议在做排序类题目时心里始终记着“排序是否会损失题目需要保留的信息”这个问题。5.5 从这道题延伸到C语言的内存管理思考做完这道题后我还想多说一点很多搜索热词里提到“C语言内存管理”“C语言指针”这类基础话题而A-B数对恰好是一个练习动态数组和指针的好场景。malloc分配、free释放、指针传参这些动作全都可以在这道题里练一遍。比如你可以自己实现一个不依赖VLA的数组输入函数再试着把二分函数改成指针版本int lower_bound(const int *a, int n, int target)指针版本能帮你建立“数组就是一块连续内存下标就是指针偏移”的直觉。这个概念一旦通了C语言很多问题都能融会贯通。做题不只是为了过OJ更是为了把这些底层机制变成肌肉记忆。我当年练这道题时特意不看模板手写了三遍二分和两遍qsort比较函数印象特别深。写完以后后面遇到类似问题我基本不再需要查资料。我个人在实际操作中的体会是A-B数对这道题最值得花时间的不是记住某个解法而是去理解“为什么暴力法会超时”“为什么排序加二分能行”“为什么哈希法要处理下标偏移”。这三个为什么想清楚了你掌握的就不是一道题而是一类查找计数问题的通用套路。下次再看到“两数之和”“三数之和”“差为C的数对”这类变体你都能很快找到切入点。