1. 从一道“珠心算测验”题看集合去重的经典陷阱

“珠心算测验”这个题目名字听起来像是考算术，实际上它是一道披着算术外衣的集合去重与枚举验证题。我第一次在题库里刷到它的时候，扫了一眼题目描述，心里想的是“这不就是两数之和的变种吗”，结果提交上去直接错了一半的测试点。后来把错误数据拉出来一看，问题出在一个非常隐蔽的地方：同一个和可能由多组不同的加数对产生，但题目只要求统计“有多少个不同的和”，而不是“有多少组加数对”。

这个区别听起来很小，但它直接决定了你用什么样的数据结构来存储结果。如果你用计数器累加，那统计的是“组数”；如果你用布尔数组或者集合来标记，那统计的才是“不同的和”。很多人第一次做这道题就栽在这里，包括我自己。

这篇文章我会从这道题出发，把它的核心逻辑、常见错误、优化思路、以及从这道题延伸出来的通用解题方法完整地讲一遍。不管你是刚开始学C语言的新手，还是已经刷了几百道题想回头巩固基础的老手，相信都能从中找到一些有用的东西。尤其是那些“明明思路对了但就是过不了”的朋友，这篇文章大概率能帮你找到那个卡住你的点。

2. 题目到底在问什么：把自然语言翻译成程序逻辑

2.1 重新读题：三个关键约束条件

先把题目用我自己的话复述一遍。给定一个正整数集合，从中选出两个不同位置的数相加，问有多少个不同的和恰好也存在于这个集合中。

这里有三个约束需要特别注意：

• 不同位置：同一个数不能和自己相加，但如果有两个位置上的数值相同，它们可以相加。比如集合里有[1, 1, 2]，位置0和位置1的两个1可以相加得到2。
• 不同的和：这是最容易出错的地方。假设集合是[1, 2, 3, 4, 5]，1+4=5，2+3=5，两个不同的加数对得到了同一个和5，但5只能被统计一次。
• 和也存在于集合中：不是统计所有可能的和，而是只统计那些“和恰好是集合中某个元素”的情况。

把这三个条件串起来，题目的本质就清楚了：在集合中枚举所有两数之和，去重之后，看有多少个和落在集合内部。

2.2 为什么“去重”是这道题的核心考点

很多人做这道题的时候，第一反应是写一个双重循环，外层遍历第一个加数，内层遍历第二个加数，然后判断和是否在集合中，如果在就计数器加一。代码大概长这样：

int count = 0; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { int sum = a[i] + a[j]; // 判断sum是否在a中 for (int k = 0; k < n; k++) { if (a[k] == sum) { count++; break; } } } }

这段代码逻辑上没错，但它统计的是“有多少组加数对的和在集合中”，而不是“有多少个不同的和在集合中”。如果集合是[1, 2, 3, 4, 5]，1+4=5和2+3=5会被统计两次，但正确答案只算一次。

这就是为什么必须引入去重机制。最直接的做法是用一个布尔数组或者哈希集合来记录“哪些和已经被统计过了”。每次找到一个符合条件的和，先检查它是否已经被标记过，如果没有，计数器加一，然后标记它。

2.3 数据范围决定了算法选择

这道题的数据范围通常不会太大，集合大小一般在100以内，元素值也在一个可控的范围内。这意味着我们不需要考虑太复杂的优化，O(n²)的枚举加上O(1)的查找就足够了。

但这里有一个细节：如果元素值可能很大（比如到10^9），那就不能用布尔数组来标记和了，得用哈希集合。不过在大多数版本的题目中，元素值都有一个明确的上限，用数组标记是完全可行的。

我个人的习惯是，拿到一道题先看数据范围，然后根据范围反推用什么数据结构。这道题如果元素值在10000以内，开一个10001大小的布尔数组就够了；如果更大，就用哈希表或者排序加二分查找。

3. 从暴力枚举到标记数组：三种解法的层层递进

3.1 最直观的暴力解法及其问题

刚才已经展示了暴力解法的基本框架，这里再把它写完整一点：

#include <stdio.h> int main() { int n; scanf("%d", &n); int a[105]; for (int i = 0; i < n; i++) { scanf("%d", &a[i]); } int count = 0; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { int sum = a[i] + a[j]; int found = 0; for (int k = 0; k < n; k++) { if (a[k] == sum) { found = 1; break; } } if (found) { count++; } } } printf("%d\n", count); return 0; }

这段代码的时间复杂度是O(n³)：两层循环枚举加数对是O(n²)，内层再遍历一遍数组判断和是否存在是O(n)。如果n=100，那大概是100万次操作，勉强能过。但如果n=1000，就是10亿次操作，肯定超时。

更重要的是，这段代码逻辑上是错的，因为它没有去重。要改成正确的版本，至少得加一个标记数组。

3.2 加入标记数组：O(n²)的正确解法

正确的做法是开一个布尔数组seen，用来标记某个和是否已经被统计过。每次找到一个符合条件的和，先检查seen[sum]是否为真，如果为假，计数器加一，然后把seen[sum]设为真。

#include <stdio.h> #include <string.h> int main() { int n; scanf("%d", &n); int a[105]; int max_val = 0; for (int i = 0; i < n; i++) { scanf("%d", &a[i]); if (a[i] > max_val) max_val = a[i]; } // 标记数组，大小为最大可能和+1 int seen[20005]; memset(seen, 0, sizeof(seen)); // 先标记集合中存在的元素 int in_set[20005]; memset(in_set, 0, sizeof(in_set)); for (int i = 0; i < n; i++) { in_set[a[i]] = 1; } int count = 0; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { int sum = a[i] + a[j]; if (in_set[sum] && !seen[sum]) { seen[sum] = 1; count++; } } } printf("%d\n", count); return 0; }

这个版本的时间复杂度是O(n²)，因为内层的查找变成了O(1)的数组访问。对于n=1000的情况，大约是50万次操作，完全没问题。

这里有一个细节需要注意：seen数组的大小要足够大，至少是最大可能和加一。如果元素值最大是10000，那两个元素相加最大是20000，所以数组大小至少是20001。我一般会开稍微大一点，避免边界问题。

3.3 排序加双指针：另一种思路

除了标记数组，还有一种思路是先排序，然后用双指针来判断和是否存在。不过对于这道题来说，双指针的优势并不明显，因为我们需要枚举所有加数对，而不是找一个特定的和。

但如果你把问题反过来想：对于集合中的每个元素target，判断是否存在两个不同的数加起来等于target。这样问题就变成了“两数之和”的变种，可以用双指针来做。

#include <stdio.h> #include <stdlib.h> int cmp(const void *a, const void *b) { return *(int *)a - *(int *)b; } int main() { int n; scanf("%d", &n); int a[105]; for (int i = 0; i < n; i++) { scanf("%d", &a[i]); } qsort(a, n, sizeof(int), cmp); int count = 0; for (int k = 0; k < n; k++) { int target = a[k]; int left = 0, right = n - 1; int found = 0; while (left < right) { if (left == k) { left++; continue; } if (right == k) { right--; continue; } int sum = a[left] + a[right]; if (sum == target) { found = 1; break; } else if (sum < target) { left++; } else { right--; } } if (found) count++; } printf("%d\n", count); return 0; }

这个版本的时间复杂度是O(n²)，因为外层遍历每个元素，内层双指针是O(n)。虽然复杂度一样，但实际运行时常数更小，因为双指针的移动次数比双重循环少。

不过这个版本有一个潜在的问题：如果集合中有重复元素，双指针可能会跳过某些合法的组合。比如集合是[1, 1, 2]，target=2，left=0，right=2，sum=1+2=3，不相等；然后right--变成1，sum=1+1=2，找到了。但如果left和right都指向同一个位置，就需要特殊处理。

所以我个人更倾向于用标记数组的版本，逻辑更清晰，不容易出错。

4. 那些年我踩过的坑：从WA到AC的完整排查记录

4.1 第一个坑：忘记去重导致答案偏大

这是我第一次做这道题时犯的错误。当时我写完暴力解法，自己测试了几个样例，发现答案都对，就提交了。结果系统返回WA，我一看通过率只有50%。把错误数据拉出来一看，集合是[1, 2, 3, 4, 5]，我的程序输出是4，正确答案是3。

为什么？因为1+4=5和2+3=5都被统计了，但5只能算一次。这就是典型的“统计组数”和“统计不同和”的区别。

提示：每次看到“有多少个不同的XXX”这种表述，第一反应就应该是去重。去重的手段可以是布尔数组、哈希集合、或者排序后去重。

4.2 第二个坑：标记数组开小了导致越界

有一次我写题的时候，看到元素值最大是100，就想当然地开了一个201大小的标记数组。结果测试数据里有一个元素是100，另一个也是100，和是200，数组下标200越界了。虽然C语言不会报错，但会访问到非法内存，导致结果不可预测。

正确的做法是：先读入所有元素，找到最大值，然后开一个2 * max_val + 1大小的数组。或者干脆开一个足够大的数组，比如20005，反正内存不要钱。

int max_val = 0; for (int i = 0; i < n; i++) { scanf("%d", &a[i]); if (a[i] > max_val) max_val = a[i]; } int seen[2 * max_val + 1]; memset(seen, 0, sizeof(seen));

4.3 第三个坑：重复元素导致的逻辑错误

如果集合中有重复元素，比如[1, 1, 2, 3]，那么1+1=2是合法的，因为两个1来自不同的位置。但如果你的代码里用了if (a[i] == a[j]) continue;来跳过相同元素，就会漏掉这种情况。

正确的做法是：只判断i != j，不判断a[i] != a[j]。因为题目要求的是“不同位置”，而不是“不同数值”。

for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { // 这里不需要判断a[i] != a[j] int sum = a[i] + a[j]; // ... } }

4.4 第四个坑：输出格式的细节

有些版本的题目要求输出“有多少个不同的和”，有些版本要求输出“这些和分别是多少”。如果是后者，那就不能只用一个计数器，还得把符合条件的和存下来，最后排序输出。

我遇到过一道类似的题，要求输出去重后的和，并且按升序排列。当时我用了一个数组来存结果，最后用qsort排序。但忘记处理重复的和，导致输出里有重复元素。后来加了一个判断：只有当seen[sum]为假时才存入结果数组。

int result[20005]; int result_count = 0; // ... if (in_set[sum] && !seen[sum]) { seen[sum] = 1; result[result_count++] = sum; } // 最后对result排序并输出

5. 从这道题延伸出的通用解题框架

5.1 “枚举加验证”类题目的通用模板

这道题本质上属于“枚举加验证”类题目：枚举所有可能的候选答案，然后验证每个候选是否满足条件。这类题目的通用框架是：

1. 确定枚举范围：哪些东西需要枚举？这道题是枚举所有加数对。
2. 确定验证条件：每个候选需要满足什么条件？这道题是和必须在集合中。
3. 确定去重机制：如果有重复候选，如何去重？这道题是用布尔数组标记。
4. 确定数据结构：用什么来存储集合和标记？这道题是数组。

把这个框架套用到其他题目上，比如“两数之和”、“三数之和”、“四数之和”，思路都是相通的。

5.2 布尔数组标记法的适用场景

布尔数组标记法是一种非常实用的技巧，适用于以下场景：

• 元素值在一个可控的范围内（比如0到10000）
• 需要快速判断某个值是否出现过
• 需要去重

它的优点是O(1)的查找和插入时间，缺点是空间消耗与值域成正比。如果值域很大（比如到10^9），就不能用数组，得用哈希集合。

在这道题中，因为元素值通常不会太大，布尔数组是最优选择。但如果题目没有给出明确的值域限制，保险起见可以用哈希集合。

5.3 时间复杂度分析的实战意义

很多人觉得时间复杂度分析只是理论上的东西，实际写代码的时候用不上。但在这道题里，时间复杂度直接决定了你能不能过。

假设n=1000，暴力解法是O(n³)=10^9次操作，肯定超时。标记数组法是O(n²)=10^6次操作，轻松通过。这就是为什么必须学会分析时间复杂度，并根据复杂度选择算法。

我个人的经验是：如果n≤100，O(n³)可以接受；如果n≤1000，O(n²)可以接受；如果n≤10^5，需要O(n log n)；如果n≤10^6，需要O(n)。

6. 代码之外的思考：这道题教会我的事

6.1 读题比写代码更重要

这道题我前前后后做了三次才完全做对。第一次错在没去重，第二次错在数组开小了，第三次才AC。回顾整个过程，我发现最大的问题不是编码能力，而是读题能力。

题目中的每一个字都是有意义的。“不同的和”这四个字，我第一遍读的时候完全没注意到，以为是“有多少组加数对”。后来仔细读了三遍，才发现自己理解错了。

所以我现在养成了一个习惯：每道题至少读三遍。第一遍快速浏览，了解大意；第二遍逐字逐句读，标记关键约束；第三遍用自己的话复述一遍，确认理解无误。

6.2 测试用例要覆盖边界情况

这道题的边界情况包括：

• 集合中没有符合条件的和（输出0）
• 集合中有多个加数对得到同一个和（去重）
• 集合中有重复元素（不同位置可以相加）
• 集合中只有一个元素（无法组成加数对）
• 集合中的元素值很大（数组要开够）

我一般会针对每种边界情况写一个测试用例，确保代码在所有情况下都能正确运行。

6.3 从一道题到一类题

做完这道题之后，我把类似的题目都找出来做了一遍，包括“两数之和”、“三数之和”、“四数之和”、“最接近的三数之和”等等。做完之后发现，这些题目的核心思路都是一样的：枚举加验证，加上适当的去重和优化。

这种“从一道题到一类题”的学习方法，比单纯刷题效率高得多。因为你不仅学会了怎么解这道题，还学会了怎么解这一类题。

7. 完整代码实现与逐行注释

7.1 最终版本的完整代码

#include <stdio.h> #include <string.h> int main() { int n; scanf("%d", &n); int a[105]; int max_val = 0; for (int i = 0; i < n; i++) { scanf("%d", &a[i]); if (a[i] > max_val) { max_val = a[i]; } } // in_set用于标记集合中存在的元素 // seen用于标记已经统计过的和 int in_set[20005]; int seen[20005]; memset(in_set, 0, sizeof(in_set)); memset(seen, 0, sizeof(seen)); for (int i = 0; i < n; i++) { in_set[a[i]] = 1; } int count = 0; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { int sum = a[i] + a[j]; if (in_set[sum] && !seen[sum]) { seen[sum] = 1; count++; } } } printf("%d\n", count); return 0; }

7.2 关键代码段的逻辑说明

第一段：读入数据并记录最大值

int max_val = 0; for (int i = 0; i < n; i++) { scanf("%d", &a[i]); if (a[i] > max_val) { max_val = a[i]; } }

这段代码的作用是读入集合元素，同时记录最大值。为什么要记录最大值？因为后面开标记数组的时候，需要知道数组的大小。虽然可以直接开一个固定大小的数组（比如20005），但记录最大值是一个好习惯，可以避免不必要的内存浪费。

第二段：标记集合中存在的元素

for (int i = 0; i < n; i++) { in_set[a[i]] = 1; }

这段代码把集合中出现的所有元素在in_set数组中标记为1。这样后面判断一个和是否在集合中时，只需要O(1)的时间。

第三段：枚举加数对并去重

for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { int sum = a[i] + a[j]; if (in_set[sum] && !seen[sum]) { seen[sum] = 1; count++; } } }

这是核心逻辑。外层循环遍历第一个加数，内层循环遍历第二个加数。注意内层循环从i+1开始，这样可以保证每个加数对只被枚举一次，同时避免了同一个位置和自己相加。

if (in_set[sum] && !seen[sum])这个条件做了两件事：首先判断和是否在集合中，然后判断这个和是否已经被统计过。只有两个条件都满足，才计数器加一，并标记这个和已经被统计过。

7.3 测试用例与预期输出

这些测试用例覆盖了去重、重复元素、边界情况等场景。每次写完代码，我都会用这些用例跑一遍，确保逻辑正确。

8. 新手常见疑问集中解答

8.1 为什么不能用两层循环直接统计

因为两层循环统计的是“有多少组加数对”，而不是“有多少个不同的和”。如果集合中有多个加数对得到同一个和，两层循环会把它们都统计进去，导致答案偏大。

8.2 标记数组到底要开多大

标记数组的大小应该至少是“最大可能的和加一”。最大可能的和是集合中最大的两个元素之和，但为了保险起见，可以直接开2 * max_val + 1。如果不想计算max_val，也可以开一个足够大的固定值，比如20005。

8.3 如果元素值很大怎么办

如果元素值可能达到10^9，就不能用布尔数组了，因为数组下标不能是10^9。这时候需要用哈希集合来存储集合中的元素和已经统计过的和。在C语言中，可以用自己实现的哈希表，或者用C++的unordered_set。

8.4 这道题和“两数之和”有什么区别

“两数之和”通常是给定一个目标值，问是否存在两个数加起来等于目标值。而这道题是枚举所有可能的和，然后看有多少个和落在集合中。两者的核心思路都是枚举加验证，但具体实现有所不同。

8.5 为什么内层循环从i+1开始

因为加数对是无序的，1+2和2+1是同一个加数对。从i+1开始可以避免重复枚举同一个加数对，同时也能避免同一个位置和自己相加。

9. 从AC到举一反三：同类题目的扩展练习

9.1 三数之和的去重版本

如果把题目改成“有多少个不同的和可以由三个不同的数相加得到，且这个和也在集合中”，那就变成了三数之和的去重版本。核心思路是一样的：枚举所有三元组，计算和，去重，验证。

for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { for (int k = j + 1; k < n; k++) { int sum = a[i] + a[j] + a[k]; if (in_set[sum] && !seen[sum]) { seen[sum] = 1; count++; } } } }

时间复杂度变成了O(n³)，如果n=100，就是100万次操作，勉强能过。如果n更大，就需要优化。

9.2 统计所有可能的和

如果把题目改成“统计所有可能的和，并输出去重后的结果”，那就需要把所有的和都存下来，最后排序输出。

int all_sums[20005]; int sum_count = 0; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { int sum = a[i] + a[j]; if (!seen[sum]) { seen[sum] = 1; all_sums[sum_count++] = sum; } } } // 对all_sums排序并输出

这个版本不需要判断和是否在集合中，只需要去重即可。

9.3 判断是否存在特定的和

如果题目改成“判断是否存在两个数加起来等于给定的目标值”，那就变成了经典的“两数之和”问题。可以用哈希表来做，时间复杂度O(n)。

int target; scanf("%d", &target); int found = 0; for (int i = 0; i < n; i++) { int complement = target - a[i]; if (in_set[complement] && complement != a[i]) { found = 1; break; } }

这个版本的时间复杂度是O(n)，比枚举所有加数对快得多。

10. 我在实际编码中的几个习惯

10.1 先写测试用例再写代码

我现在养成了一个习惯：拿到题目之后，先不急着写代码，而是先手写几个测试用例，包括正常情况、边界情况、特殊情况。然后根据测试用例来设计算法，最后才写代码。这样做的好处是，代码写完之后可以直接用测试用例验证，不用等到提交才发现问题。

10.2 用memset初始化数组

在C语言中，局部数组不会自动初始化为0，必须手动初始化。我一般用memset来初始化，因为它比循环赋值快，而且代码更简洁。

int seen[20005]; memset(seen, 0, sizeof(seen));

注意memset的第三个参数是字节数，所以要用sizeof(seen)而不是20005。如果数组是int类型，memset只能用来初始化为0或-1，不能初始化为其他值。

10.3 数组大小开大一点

我一般会把数组大小开得比实际需要的大一点，比如需要20001就开20005。这样做的好处是避免边界问题，坏处是浪费一点内存。但在竞赛编程中，内存通常不是瓶颈，所以这个习惯是利大于弊的。

10.4 用printf调试而不是断点

在竞赛编程中，我一般用printf来调试，而不是用IDE的断点功能。因为竞赛环境通常没有图形化调试器，而且printf更灵活，可以输出中间变量的值，帮助定位问题。

printf("sum=%d, in_set=%d, seen=%d\n", sum, in_set[sum], seen[sum]);

这种调试语句在定位逻辑错误时非常有用。

11. 这道题背后的数学思维

11.1 集合与多重集的区别

这道题的核心考点其实是“集合”和“多重集”的区别。集合中的元素是唯一的，多重集中的元素可以重复。题目要求统计“不同的和”，实际上是在统计一个集合的大小，而不是多重集的大小。

理解这一点之后，去重就变得很自然了：因为集合中的元素是唯一的，所以每个和只能被统计一次。

11.2 枚举的完备性

枚举法的核心是“不重不漏”。不重是指每个候选只被枚举一次，不漏是指所有候选都被枚举到。在这道题中，内层循环从i+1开始保证了不重，两层循环遍历所有i < j的组合保证了不漏。

这种“不重不漏”的思想在组合数学中非常重要，很多计数问题都是基于这个思想来解决的。

11.3 空间换时间

用布尔数组来标记已经统计过的和，本质上是一种“空间换时间”的策略。如果不使用标记数组，每次都要遍历一遍已经统计过的和来判断是否重复，时间复杂度会变成O(n³)。使用标记数组之后，判断重复的时间变成了O(1)，总时间复杂度降到了O(n²)。

这种权衡在算法设计中非常常见。很多时候，多花一点内存可以换来时间上的大幅优化。

12. 写给正在刷题的你

刷题这件事，数量固然重要，但质量更重要。与其刷一百道题每道都一知半解，不如把十道题彻底吃透。什么叫吃透？就是你能把这道题的思路讲给别人听，能写出三种不同的解法，能说出每种解法的优缺点，能举一反三解决同类问题。

这道“珠心算测验”看起来很简单，但它涉及了枚举、去重、标记数组、时间复杂度分析等多个知识点。把这道题彻底搞懂，比刷十道类似的题都有用。

我在刚开始学C语言的时候，也经历过“一看就会，一写就错”的阶段。后来发现，问题出在“眼高手低”：看题的时候觉得思路很清晰，但真正写代码的时候才发现有很多细节没考虑到。解决这个问题的方法只有一个：多写，多调试，多总结。

每做完一道题，我都会问自己三个问题：这道题的核心考点是什么？我踩了哪些坑？下次遇到类似的题，我能做得更好吗？把这三个问题的答案记下来，下次遇到同类题的时候翻出来看看，进步会非常快。

最后说一个我自己的小技巧：如果你在做这道题的时候卡住了，不妨把集合缩小到三个元素，手动枚举所有加数对，看看哪些和是重复的，哪些是不重复的。手动模拟一遍之后，再去写代码，思路会清晰很多。这个方法在我初学阶段帮了我很多次，推荐你也试试。