NOIP201401 珠心算测验

时间限制： C/C++ 1000MS，其他语言 2000MS 内存限制： C/C++ 256MB，其他语言 512MB 难度： 中等 分数： 100 OI排行榜得分：12(0.1分数+2难度)

描述

珠心算是一种通过在脑中模拟算盘变化来完成快速运算的一种计算技术。珠心算训练，既能够开发智力，又能够为日常生活带来很多便利，因而在很多学校得到普及。某学校的珠心算老师采用一种快速考察珠心算加法能力的测验方法。他随机生成一个正整数集合，集合中的数各不相同，然后要求学生回答：其中有多少个数，恰好等于集合中另外两个（不同的）数之和？最近老师出了一些测验题，请你帮忙求出答案。

输入描述

输入共两行，第一行包含一个整数 n，表示测试题中给出的正整数个数。第二行有 n 个正整数，每两个正整数之间用一个空格隔开，表示测试题中给出的正整数。

输出描述

输出共一行，包含一个整数，表示测验题答案。

用例输入 1

4
1 2 3 4

用例输出 1

提示

3<=n<=100 测验的数均不超过10000

思路：

将输入的正整数存入一个集合中，方便后续查找。
使用两层循环遍历集合中的每对数，判断集合中是否存在它们的和，如果存在，则计数器加一。
输出计数器的值。

时间复杂度分析： 假设集合中有n个数，外层循环需要遍历n次，内层循环需要遍历(n-1)+(n-2)+...+2+1=n(n-1)/2次，所以总的时间复杂度为O(n^2)。

空间复杂度分析： 使用了一个集合来存储输入的正整数，所以空间复杂度为O(n)。

实现代码如下：

n = int(input())
nums = set(map(int, input().split()))
count = 0

for num1 in nums:
    for num2 in nums:
        if num1 != num2 and num1 + num2 in nums:
            count += 1

print(count // 2)