简易题解
题目大意
给定一个包含 \(n\) 个互不相同的正整数的集合。我们需要找出这个集合中有多少个数字，恰好等于集合中另外两个不同数字的和。
思路分析
题目要求我们找出满足 A = B + C 形式的数字 A，其中 A, B, C 都是给定集合中的数字，并且 B 和 C 必须是不同的数字。
由于 \(n\) 的范围较小（\(3 \le n \le 100\)），且集合中的正整数大小不超过 \(10,000\)，我们可以采用比较直接的暴力枚举方法来解决。
具体步骤如下：
-
存储和快速查找： 为了方便查找一个数是否存在于集合中，我们可以使用一个布尔数组（或者整型数组作为布尔标记）来标记集合中的所有数。由于数的大小不超过 \(10,000\)，我们可以创建一个大小约 \(10,001\) 的布尔数组
exists，将exists[x]设为true（或1）表示数x存在于集合中。- 在读取输入的 \(n\) 个正整数时，将它们存入一个数组
a的同时，也将exists[a[i]]标记为true。
- 在读取输入的 \(n\) 个正整数时，将它们存入一个数组
-
枚举所有可能的和： 遍历集合中所有的数字对
(a[i], a[j])，计算它们的和sum = a[i] + a[j]。- 为了确保
B和C是不同的数，我们让外层循环变量i从 \(1\) 到 \(n\)，内层循环变量j从i+1到 \(n\)。这样可以保证a[i]和a[j]总是集合中两个不同的数，并且不会重复计算a[i]+a[j]和a[j]+a[i]。
- 为了确保
-
检查和是否在集合中： 对于计算出的每一个和
sum：- 检查
exists[sum]是否为true。如果为true，则说明sum这个数字也存在于原始集合中。 - 此时，
sum就是一个满足条件的数字。
- 检查
-
去重统计： 题目要求的是“有多少个数，恰好等于集合中另外两个（不同的）数之和”。这意味着如果同一个数
X可以通过不同的组合(B1+C1)和(B2+C2)得到，它也只算作一个满足条件的数。- 为了避免重复统计同一个满足条件的和，当我们发现
sum满足条件时，应该立即将其从exists标记中去除（例如，将exists[sum]设为false或0），这样即使后面有其他组合也得到了sum，也不会再次增加计数器。 - 每次找到一个满足条件的
sum并且它还未被统计过时，就将计数器ans加 \(1\)。
- 为了避免重复统计同一个满足条件的和，当我们发现
示例说明
输入：
4
1 2 3 4
- 初始化：
a = [?, 1, 2, 3, 4](这里数组从1开始)，b数组标记b[1]=1, b[2]=1, b[3]=1, b[4]=1。 - 枚举：
i=1, j=2:a[1]=1, a[2]=2.sum = 1+2 = 3.b[3]是1。ans加 \(1\) 变为1。并将b[3]设为0(防止重复统计)。i=1, j=3:a[1]=1, a[3]=3.sum = 1+3 = 4.b[4]是1。ans加 \(1\) 变为2。并将b[4]设为0。i=1, j=4:a[1]=1, a[4]=4.sum = 1+4 = 5.b[5]是0。不满足。i=2, j=3:a[2]=2, a[3]=3.sum = 2+3 = 5.b[5]是0。不满足。i=2, j=4:a[2]=2, a[4]=4.sum = 2+4 = 6.b[6]是0。不满足。i=3, j=4:a[3]=3, a[4]=4.sum = 3+4 = 7.b[7]是0。不满足。
最终答案 ans = 2。
代码注释
#include<bits/stdc++.h> // 包含所有标准库，方便快速编程
using namespace std; // 使用标准命名空间int a[105]; // 定义一个大小为105的整型数组a，用于存储输入的n个正整数。// 题目中n最大为100，所以105足够。
int b[20005]; // 定义一个大小为20005的整型数组b。// b[x] = 1 表示数字x在原始集合中出现过，b[x] = 0 表示未出现或已被统计。// 集合中的正整数最大10000，两数之和最大约20000 (9999+9998)，所以20005足够。int main()
{int n; // 定义整型变量n，表示输入的正整数个数。cin>>n; // 从标准输入读取n的值。// 读取n个正整数，并将其存储在数组a中，同时在数组b中标记它们的存在。for(int i=1;i<=n;i++) // 循环n次，从a[1]到a[n]存储。{cin>>a[i]; // 读取第i个正整数。b[a[i]]=1; // 将数组b中对应a[i]的索引位置设为1，表示a[i]这个数存在于集合中。}int ans=0; // 定义一个整型变量ans，用于存储最终的答案（满足条件的数的个数），初始化为0。// 外层循环，枚举第一个加数a[i]for(int i=1;i<=n;i++) {// 内层循环，枚举第二个加数a[j]。j从i+1开始，保证a[i]和a[j]是集合中不同的两个数，// 且避免重复计算a[i]+a[j]和a[j]+a[i]。for(int j=i+1;j<=n;j++) {// 检查它们的和 a[i]+a[j] 是否在原始集合中，并且该和还没有被统计过。// b[a[i]+a[j]] == 1 表示和存在于集合中且未被计入答案。if(b[a[i]+a[j]]==1) {ans++; // 如果满足条件，则答案加1。b[a[i]+a[j]]=0; // 将这个和在b数组中的标记设为0，表示它已经被统计过了，防止重复计数。}}}cout<<ans<<endl; // 输出最终的答案。return 0; // 程序正常结束。
}