在准备蓝桥杯C算法提高的过程中我遇到的第一道“看起来不难其实有坑”的题目就是珠心算测验。题目名字听上去像是给小学生准备的珠心算练习实际上它考的是枚举、哈希和去重不少第一次写的人会在这里丢分。这篇文章把我从最初的三层循环暴力版本一路优化到最终通过的完整过程复盘出来包括三个我亲自踩过的坑和一组验证用的测试用例。如果你正在刷蓝桥杯的算法提高题或者想在C里试试“两数之和”这类问题的变体这篇应该能帮上忙。我先说结论这题真正的考点不是珠心算而是去重。整个题解的核心只有两句话——枚举集合中任意两个不同数的组合把它们的和标记为“合法”最后数一数原集合中有多少个数刚好落在这些合法值里。1. 珠心算测验这道题到底在问什么1.1 题目回放别被“珠心算”三个字带偏题目的大致意思是老师会随机生成n个正整数组成一个集合。学生需要数一数这个集合中有多少个数恰好等于集合中另外两个数的和。比如集合是 {1,2,3,4}那么3等于124等于13所以答案是2。注意看题目的用词“另外两个数”意味着必须是两个不同位置上的数而不是同一个数拿自己加自己。很多人第一眼会觉得这题很简单但一旦写代码就会发现有两个隐藏条件第一“另外两个数”可以是两个数值相同的数吗如果集合里有两个1那么112是可以的因为两个1的位置不同第二同一个目标数如果被多组组合表示比如 {1,2,3,4,5} 里的5既能拆成14也能拆成23但它只能被计数一次。这两个隐藏条件不处理好提交就会出错。1.2 题眼枚举、去重、集合三件事从算法层面拆解珠心算测验其实做了三件事枚举找出所有合法的“两个不同数”的组合。这里最常见的写法是双重循环让第二个下标从第一个下标1开始这样天然避免了同一个位置被用两次。判断计算两个数的和判断这个和是否还存在于原集合中。去重如果一个和能被多种组合表示那么目标数只能在答案中贡献一次不能重复累加。这三件事里“枚举”和“判断”都很直观真正容易翻车的是“去重”。我在第一次写的时候就是把514和523分别计了两次结果样例都没过。1.3 这类题在竞赛中的位置蓝桥杯的题目风格比较两极分化有的是纯算法难题有的则是“给你一个看似简单的场景实际上考验基础代码的严谨性”。珠心算测验属于后者它经常出现在基础题库或者算法提高模块里作为枚举和哈希的入门练习题。对准备蓝桥杯C组的人来说这道题的意义不在于它本身有多难而在于它能帮你检验三样东西会不会用unordered_set知不知道数组去重以及能不能从O(n^3)的暴力思路里跳出来。这三样恰恰是蓝桥杯初级到中级选手最需要的基本功。2. 第一版暴力解法三层循环为什么能过也可能过不了2.1 第一版代码莽上去再说我第一次看到这个题第一反应就是暴力三层循环外层枚举每一个可能的“目标数”内层两层枚举所有加数对如果找到一组加数的和等于目标数就标记这个目标数已经满足条件。直接看代码#include bits/stdc.h using namespace std; int main() { int n; cin n; vectorint a(n); for (int i 0; i n; i) { cin a[i]; } bool used[10005] {false}; // used[k] 表示第k个数是否已经被计入答案 int ans 0; for (int k 0; k n; k) { // 目标是 a[k] for (int i 0; i n; i) { // 加数1 for (int j i 1; j n; j) { // 加数2保证两个加数位置不同 if (a[i] a[j] a[k] !used[k]) { ans; used[k] true; break; } } } } cout ans endl; return 0; }这段代码的思路是“查目标”对每个目标数a[k]把所有可能的加数对都试一遍一旦找到就立刻标记并跳出。这里有两个细节我特意处理了j从i1开始保证两个加数是不同位置的数用used数组保证同一个目标数不会被重复统计。2.2 三层循环的复杂度账三层循环的时间复杂度是O(n^3)。如果n100循环次数是10^6级别现代计算机跑起来毫无压力如果n1000循环次数是10^9级别大概率会超时。蓝桥杯的原题数据一般给得比较保守n可能只有100或者更小所以很多人用暴力也能AC。但我们刷题不能只盯着“过不过”看尤其是“算法提高”方向的题目。出题人把这道题放在提高模块绝不是希望你用三层循环混过去。一旦某个测试点把n调到500甚至1000暴力的性能就会被立刻打回原形。这也是我在复盘时坚持要写优化版本的原因。2.3 暴力里最容易忽略的重复计数暴力代码的used数组帮我们解决了一个大问题同一目标数不重复计数。但如果我一开始就把代码写成for (int k 0; k n; k) for (int i 0; i n; i) for (int j i1; j n; j) if (a[i]a[j]a[k]) ans;那么对于 {1,2,3,4,5} 这个样例5 会被数两次因为14和23都等于5。这种错误非常隐蔽因为小数据可能恰好没触发等数据一多就WA了。暴力版的另一个问题是哪怕加了used它依然做了大量无效枚举。比如目标数很小时我们仍然会跑完所有加数对才放弃白白消耗时间。所以想要真正稳定地拿分必须改变思路。3. 从暴力到高效两种主流解法的选型逻辑3.1 思路切换把“查目标”换成“标和”暴力解法是外层枚举目标、内层找加数。我们可以把顺序彻底反过来先枚举所有加数对算出它们的和然后判断这个和是否在原集合中。如果存在就把这个和标记为“合法值”最后再统计原集合中有多少个元素正好是合法值。这个思路的直观理由是两个数的组合数是O(n^2)这个规模是可以接受的。我们不再需要第三层循环去“对答案”只需要用哈希表O(1)查一个和是否在集合里。整体复杂度一下子从O(n^3)降到O(n^2)。3.2 排序二分的写法思路正确但稍显笨重既然要判断“和是否在原集合中”第一个自然想到的方案就是排序二分查找。把原数组排序后每算出一个和就用二分在有序数组里找它。代码大概是这样的#include bits/stdc.h using namespace std; const int MAXV 10005; int main() { int n; cin n; vectorint a(n); for (int i 0; i n; i) cin a[i]; sort(a.begin(), a.end()); bool ok[MAXV] {false}; for (int i 0; i n; i) { for (int j i 1; j n; j) { int sum a[i] a[j]; int l 0, r n - 1; while (l r) { int mid (l r) / 2; if (a[mid] sum) { if (sum 0 sum MAXV) ok[sum] true; break; } else if (a[mid] sum) { l mid 1; } else { r mid - 1; } } } } int ans 0; for (int x : a) { if (x 0 x MAXV ok[x]) ans; } cout ans endl; return 0; }这里我用了一个bool ok[MAXV]来标记哪些和值已经被找到过目的是去重。排序二分的总复杂度是O(n^2 log n)用是可以用但有两个问题第一二分查找在一组枚举里反复执行代码比哈希版长第二如果和的值域很大bool ok[]就开不下了得改用哈希表。3.3 哈希集合的写法最推荐的做法C标准库里的unordered_set正好可以同时解决“O(1)判断存在”和“动态扩大值域”两个问题。我们先用一个unordered_set存下整个原集合然后枚举加数对算出和后直接用count判断。只要存在就把这个和放进另一个valid集合中。最后遍历原数组数一数有多少个元素出现在valid中。#include bits/stdc.h using namespace std; int main() { int n; cin n; vectorint a(n); unordered_setint nums; // 存原集合用于快速判断和是否存在 for (int i 0; i n; i) { cin a[i]; nums.insert(a[i]); } unordered_setint valid; // 存所有可以表示为两数之和的值 for (int i 0; i n; i) { for (int j i 1; j n; j) { int sum a[i] a[j]; if (nums.count(sum)) { valid.insert(sum); } } } int ans 0; for (int x : a) { if (valid.count(x)) ans; } cout ans endl; return 0; }代码很短核心逻辑只有三个步骤预处理集合、枚举组合、统计答案。这个版本也是我最后提交AC的版本。3.4 两种方案怎么选一张表看清楚方案时间复杂度空间复杂度去重方式代码量适用场景三层暴力O(n^3)O(n)布尔数组标记目标最少仅限n≤100排序二分O(n^2 log n)O(n)布尔数组标记和值中等值域已知且较小哈希集合O(n^2)O(n)unordered_set最少通用性最强从蓝桥杯的实际数据量来看哈希集合是最平衡的选择。它不依赖值域也不依赖排序遇到重复数字时依然能通过valid.count(x)正确统计每个元素。如果你愿意还可以把unordered_set换成set但set的查询是O(log n)整体会变成O(n^2 log n)所以优先用哈希。4. C代码实现与提交复盘4.1 最终代码注释版每一步在干什么最终代码我在上面已经给出这里再做一个带注释的展开版本方便直接抄作业#include bits/stdc.h using namespace std; int main() { // ---------- 输入 ---------- int n; cin n; vectorint a(n); unordered_setint all; for (int i 0; i n; i) { cin a[i]; all.insert(a[i]); // 记录所有数字方便后面判断两数之和是否存在 } // ---------- 枚举所有加数对 ---------- unordered_setint sums; // 记录能表示成两数之和的那些值 for (int i 0; i n; i) { for (int j i 1; j n; j) { int s a[i] a[j]; if (all.count(s)) { sums.insert(s); // 用集合自动去重同一个和只保留一次 } } } // ---------- 统计原集合中有多少个数在sums里 ---------- int ans 0; for (int x : a) { if (sums.count(x)) { ans; } } cout ans endl; return 0; }注意j从i1开始这保证了我们枚举的是“两个不同位置的数”。sums的作用是去重比如 {1,2,3,4,5} 里5既能由14得到也能由23得到第一次算到5时插入了sums第二次再算到5时插入的其实是重复元素unordered_set自动忽略最终遍历原数组时5只会贡献一次答案。4.2 提交时的三个坑每一个我都踩过第一个坑是重复计数。我最初在枚举加数对时每找到一组就ans没有做任何去重导致 {1,2,3,4,5} 里5被数了两次。解决方式是引入sums集合先把所有合法的和存起来最后统一统计。这个坑是最典型的十个没AC的人里至少有五个倒在这里。第二个坑是把“不同位置的数”理解成了“不同数值的数”。老实说如果集合里没有重复数字这两种理解是一样的但一旦出现重复数字比如 {1,1,2,3}2可以由两个1相加得到这里的两个1虽然值相同但位置不同应当是合法的。我的代码里用ji1保证位置不同所以这种情况能正确处理。第三个坑是误用了数组下标。有一版代码我图省事想把ok[sum]当成标记数组但忘了检查sum是否会超出数组边界。蓝桥杯的测试数据里如果数值大到一定程度越界访问会直接导致运行时错误。后来我改用unordered_set既避免了越界又不用提前开大数组。4.3 测试样例与结果验证我在本地用了下面这些数据验证代码结果全对输入输出说明4换行1 2 3 423124135换行1 2 3 4 533、4、5其中5只算一次3换行1 2 31只有3126换行1 1 2 3 43211312413两个1都能作为加数最后一个用例故意加了重复的1用来验证“不同位置”的处理。如果你的平台有在线评测把这些样例丢进去基本够用了。真正递交前最好再写一个随机生成小数据的脚本把暴力版和哈希版的结果对比一下确保没有边界遗漏。5. 从这道题延伸出的竞赛经验5.1 从珠心算测验到“两数之和”变体珠心算测验本质上是一个“两数之和”的变体。经典的“两数之和”问题是问给定数组和目标值找到两个数的下标使它们的和等于目标值。而这题反过来了给定数组问数组中有多少个数可以拆成另外两个数之和。这个反转非常有意思。它提醒我在做算法题时遇到“有没有”“有多少”“是否存在”一类的问题优先考虑哈希表遇到“所有组合”一类的问题优先考虑枚举。两者结合就是枚举组合哈希查询。这个套路在蓝桥杯的很多题里都能看到比如一些“搭积木”“凑数字”类问题本质上都是同一个模板。5.2 蓝桥杯刷题的正确姿势别满足于AC我见过很多刷题的人一道题暴力AC之后就再也不看了。但“能过”和“会了”是两回事。碰到珠心算测验这类题我更建议按这个流程走先写最直观的暴力版本确认自己理解题意没偏。看数据范围判断暴力是否可能超时。如果可能超时想一想暴力慢在哪里能不能用空间换时间。用哈希或二分写一版优化解和暴力版对拍。把这个过程中踩过的坑记录到自己的错题本里。这套流程看着麻烦但坚持下来刷题效率反而更高。因为你不是在背题而是在积累一套解决问题的通用方法。5.3 一个人的刷题之路要耐得住性子作为一个在蓝桥杯之路上踩了不少坑的人我最大的体会是算法能力的提升不是靠某一道题突然顿悟而是靠几十道、上百道这样的小题慢慢磨出来的。珠心算测验这道题很普通但它让我养成了“先分析复杂度再动手写代码”的习惯也让我记住了unordered_set在去重场景里的威力。如果你正处在刷题初期遇到这种“看了答案觉得简单自己写却总差一点”的题不用沮丧写第二遍、第三遍就好了慢慢就稳了。最后分享一个小技巧枚举加数对的时候永远让j从i1开始。这个习惯能帮你规避掉一大半“同一个数用两次”“两个相同位置相加”的问题省下的调试时间非常可观。希望这篇复盘能帮你在蓝桥杯的路上少走一点弯路。