P4696 珠心算测验（【基础】）

解题思路

题目问集合中有多少个数，恰好等于集合中另外两个不同数的和。集合里的数互不相同，所以我们可以枚举任意两个不同的数，算出它们的和，如果这个和也在集合里，就说明它符合条件。下面分三步实现。

**第一步，读入并标记。**读入 n 个数存进 nums 数组，同时用 isPresent 数组记录每个数是否在集合中：isPresent[nums[i]] = 1。

**第二步，枚举数对。**两重循环枚举所有不同的数对 i 和 j，j 从 i+1 开始，避免同一个数对自己和自己配对。算出它们的和 sum = nums[i] + nums[j]。

**第三步，判断与去重。**如果 sum 也在集合里（isPresent[sum] 为真），并且这个和还没统计过（counted[sum] 为 0），就把它标记 counted[sum] = 1，答案 answer 加一。

为什么需要 counted 去重？同一个和可能由多组数对得到，比如 1+2=3 和 2+1=3 都能得到 3，但题目问的是"集合中有多少个数"满足条件，是按数统计的，所以同一个和只能算一次。

打个比方：就像找拼图，看看哪些数能由另外两块拼出来。数据规模 n 不超过 100，两重循环非常轻松。

边界情况：集合里的数最大不超过 10000，两个数相加最大是 20000，所以标记数组开 20005；判断 sum <= 20000 防止数组越界。

参考代码

// P4696 珠心算测验：统计集合中有多少个数恰好等于另外两个不同数之和
#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int nums[105];
    int isPresent[20005] = {0};   // 某数是否在集合中
    int counted[20005] = {0};     // 该和是否已经统计过
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
        isPresent[nums[i]] = 1;
    }
    int answer = 0;
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++) {
            int sum = nums[i] + nums[j];
            if (sum <= 20000 && isPresent[sum] && !counted[sum]) {
                counted[sum] = 1;   // 同一个和只算一次
                answer++;
            }
        }
    cout << answer << endl;
    return 0;
}

复杂度分析

两重循环枚举所有数对，时间复杂度 O(n²)，n 最大 100。空间上需要两个长度 20005 的标记数组，是 O(20000)。