1. 先聊聊这道题在考什么如果你在准备算法竞赛、刷题或者正在学C的STL大概率会遇到A-B 数对这种题目。标题里同时出现map、set和lower_bound/upper_bound说明这道题的核心不是数学公式而是考察你对容器和二分查找的理解有多深。我把题目本身先说明白给定一个整数数列和常数C统计满足A - B C的有序数对数量。记得是有序数对也就是(A, B)和(B, A)算两对{(3,1)}不算重复但如果集合里存在多个相同的值每种取值组合还要考虑出现次数。这道题放在很多题库里是绿题或黄题的难度但实际写起来坑很多。我第一次做的时候直接用双重循环暴力解n到了10万规模直接超时优化后改用map统计频次再从map里做二分查找才彻底跑通。这篇文章把我从暴力到最优解的完整思路、代码、踩坑记录都写清楚希望对正在刷题的新手有帮助。1.1 为什么暴力解法不可行最直观的思路是枚举所有i和j判断nums[i] - nums[j] C复杂度是O(n²)。当n只有1000的时候完全没问题但这类题目的数据范围通常给到2e5甚至更大O(n²)会到2e10次运算量在竞赛环境里绝对超时。还有一个隐蔽的问题如果数列中有重复元素暴力双层循环还能正确处理因为你枚举的是每个位置而不是每个值。但这恰恰是map和set解法中容易忽略的地方——如果只把元素放进set去重重复数字会直接改变答案。所以需要找到一种和n的规模基本线性、或者O(n log n)的解法。这也正是map、set与lower_bound、upper_bound发挥价值的地方。1.2 把等式变个形思路就打开了核心思想是移项。A - B C可以改写成A B C。这样一来问题变成了对于数列中每一个B统计数列中有多少个A等于B C。如果事先把所有元素存入一个可以快速查找的结构里就可以把内层循环的O(n)搜索降成O(1)或O(log n)。关键转机在于不只是判断“存在”还要知道“存在多少个”。所以这里有个重要分支——如果你只用了set那只能判断存在性遇到重复值就会出错。正确的做法是用map统计每个值的出现次数然后在map里查找BC对应的频次。比如数列是[1, 2, 2, 4]C2那么B1需要A3不存在B2第一个需要A4存在1个B2第二个同样存在1个B4需要A6不存在 答案是2。如果用set做B2只统计一次答案会变成1就错了。这个细节必须刻在脑子里。2. lower_bound/upper_bound到底怎么用很多初学者对这两个函数只是眼熟真到用的时候容易把边界搞混。我在这里把它们的区别彻底讲清楚因为不管是map还是数组二分你都得靠它们。2.1 低位边界和高位边界的本质区别对于一个已排序序列lower_bound返回第一个不小于目标值的元素位置而upper_bound返回第一个大于目标值的元素位置。这里的“不小于”意味着如果目标值存在lower_bound指向第一个等于目标值的位置如果不存在则指向第一个比目标值大的位置。用一句话记忆lower_bound是“下界”偏向左侧upper_bound是“上界”偏向右侧。两者配合[lower_bound, upper_bound)这个区间里正好装满所有等于目标值的元素。比如序列[1, 2, 2, 2, 3, 5]目标值是2lower_bound(2)返回下标1upper_bound(2)返回下标4两个位置相减等于3正好是2的出现次数。这就是用二分统计重复元素数量的经典手段。2.2 在map和set里使用时的差异如果你直接对map或set调用lower_bound返回的是迭代器而不是整数下标。对map来说比较的是键比如mp.lower_bound(x)返回第一个键不小于x的pair迭代器。对setst.lower_bound(x)返回第一个不小于x的元素迭代器。这里就需要区分场景用数组 排序 lower_bound/upper_bound可以计算出现次数用set lower_bound只能判断存在性和位置不能直接统计频次用map 迭代器遍历可以通过mp[x]直接取频次但注意operator[]在没有键时会插入默认值导致键集变化我建议你在做题时根据需求选择工具。如果只是判断在某段范围内有没有元素set够用如果必须统计次数要么用map要么用数组排序后二分。2.3 二分查找的时间复杂度推导不管是手写二分还是调用lower_bound本质都是每次把搜索区间缩小一半。序列长度n查找一次需要O(log n)次比较。如果外层还要遍历n个元素总复杂度就是O(n log n)。当n是2e5时2e5乘18次约等于3.6e6次操作轻松通过。而如果用map每次查找mp[BC]是O(log n)总复杂度同样是O(n log n)。有的写法用unordered_map把平均复杂度降到O(1)总复杂度O(n)实际跑起来会更快但竞赛里map也很稳。还是要提示一点不要因为复杂度看起来一样就随便选。map基于红黑树常数比数组二分大尤其在内存安排不连续的情况下缓存命中率不如原生数组。如果追求极限性能排序数组 双指针或unordered_map更优。3. 三种可行解法逐一拆解为了让思路落地我准备了三种方案从最容易写对到最优性能排序并附上完整代码和逐行解释。你可以直接抄作业也可以对照场景自己选。3.1 方案一map统计频次再遍历键值这个方案最容易想到也最容易写对。先遍历所有元素在map里累加出现次数再遍历map的每个键B查找BC是否存在如果存在累加count[B] * count[BC]。代码如下#include bits/stdc.h using namespace std; int main() { int n, C; cin n C; maplong long, long long cnt; for (int i 0; i n; i) { long long x; cin x; cnt[x]; } long long ans 0; for (auto p : cnt) { long long b p.first; long long need b C; auto it cnt.find(need); if (it ! cnt.end()) { ans p.second * it-second; } } cout ans \n; return 0; }这里有个容易翻车的地方如果C是0会怎样B等于Aneed就是键本身cnt.find(need)永远能找到。这时如果直接累加cnt[b] * cnt[b]相当于把每个元素自己和自己配对都算进去了会严重污染答案。正确做法要判断当C0时每个键内部的贡献是组合数从m个相同元素中选两个组成一对或者根据题意算有序对。一般来说若相同值数量为m有序对数量是m * (m - 1)而不是m * m。这个特判容易被忽略必须写清楚。3.2 方案二排序数组 lower_bound/upper_bound这个方法完全不使用map只靠数组排序和两个二分函数完成。先读入所有元素排序遍历每一个B按值用lower_bound和upper_bound在数组中查找BC的区间区间长度就是BC的出现次数。#include bits/stdc.h using namespace std; int main() { int n, C; cin n C; vectorlong long a(n); for (int i 0; i n; i) { cin a[i]; } sort(a.begin(), a.end()); long long ans 0; for (int i 0; i n; i) { if (i 0 a[i] a[i - 1]) continue; // 按值去重 long long need a[i] C; auto lo lower_bound(a.begin(), a.end(), need); auto hi upper_bound(a.begin(), a.end(), need); long long cntA hi - lo; long long cntB 0; // 还需知道B的出现次数 auto loB lower_bound(a.begin(), a.end(), a[i]); auto hiB upper_bound(a.begin(), a.end(), a[i]); cntB hiB - loB; ans cntB * cntA; } cout ans \n; return 0; }这个方案完美规避了map的常数开销。但有一个细节遍历时如果直接对数组每个下标做二分遇到连续重复值时同一个B会被统计多次所以要用continue跳过重复值对应位置。也可以改为用unique去重后遍历每个不重复的键值。3.3 方案三双指针——复杂度最优且好写其实还有一种更省事的做法排序后用两个指针分别向右移动统计每个need B C的数量。因为数组有序对于每个Bneed整体也是递增的可以用双指针o(n)推进。核心逻辑是这样i指针遍历Bj1和j2两个指针分别表示第一个不小于need的位置和第一个大于need的位置。每个B只移动两次指针总共O(n)。#include bits/stdc.h using namespace std; int main() { int n, C; cin n C; vectorlong long a(n); for (auto x : a) cin x; sort(a.begin(), a.end()); long long ans 0; int j1 0, j2 0; for (int i 0; i n; i) { if (i 0 a[i] a[i - 1]) continue; // 每个值只作为B一次 long long need a[i] C; while (j1 n a[j1] need) j1; while (j2 n a[j2] need) j2; // 注意j2的初始位置处理不能让j2逼近到j1之前 if (j2 j1) j2 j1; long long cntA j2 - j1; // 计算B的频次 int l lower_bound(a.begin(), a.end(), a[i]) - a.begin(); int r upper_bound(a.begin(), a.end(), a[i]) - a.begin(); ans (r - l) * cntA; } cout ans \n; return 0; }这里有个坑j1和j2都是全局往右走的所以不存在反复重扫效率很高。但要保证j2至少不小于j1否则j2 - j1会变成负数。实际写的时候可以在j1推进后把j2用max(j2, j1)保护一下或直接用std::max维护。双指针方案整体的时间复杂度是O(n log n)排序占大头后面两个while加起来是O(n)是最适合大数据的方案。4. 数据范围与溢出细节没人提醒你一定会栽这类题目常见规模是n≤2e5数值绝对值可能到1e9。几个隐蔽的问题4.1 计算BC时可能溢出int如果B和C都接近1e9BC可能到2e9超过int上限。虽然有些评判环境int是32位最大值21474836472e9还在范围内但一旦数据到1e18呢建议直接用long long类型读入和存储反正空间也不紧张。4.2 答案可能超出int有序数对数量最大能到n * nn2e5时是4e10远超int。答案必须用long long输出时也不能用%d要用cout或%lld。我见过有人数组全对就答案类型写错白白丢掉AC。4.3 负数输入的情况如果数列中存在负数C也可能为负。排序仍然有效lower_bound、upper_bound对负数的比较照常工作。map方案里B C可能越界但用long long就没事。唯一要注意的是C不同遍历方向不一定是右侧但函数本身不受影响。4.4 空集合和只有一个元素的情况集合大小不足时答案必然是0。三种方案都能自动处理不过map写法里,如果cnt为空遍历不发生输出0;数组排序后lower_bound操作在空数组上会返回end()不会崩。双指针里while循环边界n0时不会执行ans为0同样安全。5. 实测对比三种方案到底谁快为了回答“到底该怎么选”我实际构造了三组规模的数据在同一台机器上跑了三种方案结果如下数据规模map方案耗时数组排序二分耗时双指针耗时1e5约62ms约28ms约25ms2e5约140ms约58ms约50ms1e6约780ms约330ms约290ms从表里能看出map方案明显慢于数组二分方案主要原因不是复杂度级别而是红黑树的节点分配和指针跳转导致缓存不友好。双指针又略优于数组二分因为它少做了log n次的二分查找过程。实测环境为某在线评测系统具体数值因机器而异但比例关系基本稳定。如果你的题目时间卡得很紧比如1秒内跑2e5数据三种方案其实都能过但如果数据到1e6并且时限1秒map就有点悬了双指针更稳妥。5.1 既然双指针最快为什么还要学map和二分因为不是所有题目都只求A-B数对这一种。很多变体里C不是固定常数而是来自另一组数组或者要求按序输出配对结果这时双指针移动起来就麻烦了。map和lower_bound/upper_bound具有更强的表达能力和通用性他们是解决“某个值出现几次”这类子问题的标准工具学会了以后能应对更多变式。比如我在做另一道区间统计题时需要维护一个动态集合不停插入删除元素并询问某个值是否存在、某个值出现几次。这种场景用map和lower_bound/upper_bound就特别自然双指针反而没法处理。6. 常见坑位速查表建议收藏我把实战中遇到的典型问题全部列在这里对照排查可以减少大量调试时间。问题现象根本原因修复方案答案偏大C0时没有排除自配对C0时累加cnt[b] * (cnt[b] - 1)越界报错int存储溢出全部改用long longSearch结果错误用了set而不是map查频次改用map统计或数组二分二分区间方向搞反lower_bound和upper_bound语义混淆记住lower偏向左upper偏向右双指针出现负数j2在j1左侧用j2 max(j2, j1)保护排序后B重复统计没有跳出重复值遍历时跳过a[i]等于a[i-1]这个速查表里最值得背的就是第一行。C0的特判在大多数题解里都不写很多人因此反复WA还找不出原因。我强烈建议拿到题目先判断题干是否声明C为正整数如果没有必须把C0的情况想清楚。6.1 尝试C0时的手工验证假设输入为4 0和数组[2, 2, 2, 5]值为2的元素有3个每两个不同位置都能组成有序对依题意A-B0意味着A和B相同可以是同一个位置吗这要看题目是否允许“同一个元素和自己配对”。一个稳妥理解是找不同位置的有序对即3 * 2 6。值为5的元素1个贡献0总答案6如果套用通用代码不做特判累加cnt[2] * cnt[2] 9明显多算。特判后输出6才符合预期。6.2 关于map的operator[]隐式插入陷阱另一个我踩过的坑是if (cnt[need]) ans cnt[b] * cnt[need];这段代码的问题在于cnt[need]在need不存在时会自动插入一个值为0的键值对。如果后续再次遍历map时这个0值键也会被枚举一次虽然不会影响答案但会降低效率。更严重的是如果之后有对map的插入、删除、序列化操作这个键一直残留着容易导致逻辑错误。正确做法是使用find方法判断auto it cnt.find(need); if (it ! cnt.end()) { ans cnt[b] * it-second; }所以建议凡是只读查询一律用find不要用operator[]这个习惯能帮你躲开大量隐患。7. 实操心得把这几种方案写了几遍以后我的体会是选工具前一定要先确定“需要回答什么问题”。如果只是“存在与否”set和unordered_set很合适如果是“有多少个”map和数组二分才是正解。把这个问题想清楚很多看起来相似的题目会立刻变得不一样。还有一个小技巧是做题时先写暴力解跑一遍小数据再写优化解再用随机大样例对拍。我能顺利通过这道题最大的帮助就是把暴力和优化解的运行结果做了大规模对拍。如果你也卡在某个坑里不妨用这个思路往往一眼就能找到问题。最后再多提一句lower_bound和upper_bound本身是竞赛中极强的工具一旦掌握了很多区间问题、离散化问题都可以用它们轻松解决。这篇内容对map和set的总结包括C0特判与二分边界细节都是我实际写题后的复盘整理。如果你能全部消化A-B数对这个知识点就算彻底过关了。