时空复杂度之珠心算测验
问题
珠心算是一种通过在脑中模拟算盘变化来完成快速运算的一种计算技术。珠心算训练， 既能够开发智力，又能够为日常生活带来很多便利，因而在很多学校得到普及。
某学校的珠心算老师采用一种快速考察珠心算加法能力的测验方法。他随机生成一个正整数集合，集合中的数各不相同，然后要求学生回答:其中有多少个数，恰好等于集合中另外两个(不同的)数之和?
最近老师出了一些测验题，请你帮忙求出答案。
【输入】
输入文件名为 count.in。
输入共两行，第一行包含一个整数 n，表示测试题中给出的正整数个数。
第二行有 n 个正整数，每两个正整数之间用一个空格隔开，表示测试题中给出的正整数。
【输出】
输出文件名为 count.out。
输出共一行，包含一个整数，表示测验题答案。
【输入输出样例】
count.in
4
1 2 3 4
count.out
2
【样例说明】
由 1+2=3，1+3=4，故满足测试要求的答案为 2。注意，加数和被加数必须是集合中的 两个不同的数。
【数据说明】
对于 100%的数据，3 ≤ n ≤ 100，测验题给出的正整数大小不超过 10,000。
通过分析问题，我们应该应用i,j,k三个变量进行三重循环，i从1到100，j从i+1到100，k从j+1到100，寻找a[i]=a[j]+a[k]即可，总的运行时间的复杂读为百万级。从而得出第一种算法：
方法一：
#include<stdio.h>#include <stdlib.h> int a[101]={0};int n,ans=0;int main(){int i,j,k;scanf("%d",&n);for(i=1;i<=n;i++ ){scanf("%d",&a[i]);}for(i=1;i<=n;i++){bool flag=0;for(j=i+1;j<=n;j++){for(k=j+1;k<=n;k++){if(a[i]==(a[j]+a[k])){flag=1;break;}}if(flag==1){ans++;break;}}}printf("%d\n",ans);}
那么，如果将数据量从100变为10000，测试数据大小从10000变为1000000，那么使用上面的算法，时间复杂度将达到1012。这时，我们可以定义a[1000001]的数组，用下标表示所要输入的数字，其值为1记录所输入的数字，为0表示未输入该数字。这样可以牺牲空间换取时间，判断一个整数i是否有其它两个整数的和，则变为：i从达到小循环，j从i-1到i/2循环，只需判定a[i]是否为1，a[j]+a[i-j]是否为2，即i，j，i-j都是输入的数字。此时时间复杂度小于1010。
方法二：
#include<stdio.h>#include <stdlib.h> int a[1000001]={0};int n;int main(){int i,j,x,ans=0;scanf("%d",&n);for(i=1;i<=n;i++){scanf("%d",&x);a[x]++;}for(i=1000000;i>0;i--){if(a[i]==0)continue;for(j=i-1;j>i/2;j--){if(a[j]+a[i-j]==2){ans++;break;}}}printf("%d\n",ans);}
