今天课程的第二个题目是判定是否存在两数字和为x，这个题目要求将时间复杂度限定为O（nlogn），我自己想到了三个算法，一个个来说吧，先说第一个：

问题描述：输入n个数，求给定数组中是否存在两个数，他们的和为x

输入数据：元素个数n，和x，数组a

输出数据：如果存在两个数则输出那两个数，否则输出“No Answer！”

算法分析：对于一般情况下，如果用最原始的方法就是枚举那两个数（两重for循环），当然这个算法的时间复杂度肯定不符合我们的要求，是O(n^2)，这里需要O(nlogn)就要想点方法了。我想到的第一个方法是如果我们给这个数组排好序，那么，我们可以构造一个b数组，其中b[i]=x-a[i]，这样b数组就是逆序的了，这时候我们的任务就是判定a[j]=b[i](i!=j)的存在性了，因为a[j]=b[i]可以转换为a[j]=x-a[i]，即a[i]+a[j]=x为我们所需要的式子。判定两个有序的数组是否具有位置不同的相等元素可以在O(n)的时间那完成，这样加上排序的花费，总的算来总的时间复杂度就是O(nlogn)了，满足我们的需求。至于如何在O(n)的时间那完成相等元素的检索，这个比较简单，首先a是升序的，b是降序的，这样我们可以设置两个标点i和j分别指向a和b的最小元素(i=0,j=n-1)，这样每次判断a[i]和b[j]，如果相等则找到，否则如果a[i]大则j--（让b[j]变大），如果a[i]小则i++(让a[i]变大），这样知道i和j相等还没找到的话就退出，表明没有符合题意的解。这个算法的缺点就是需要O(n)的附加空间复杂度，如果我们进行优化就可以使得算法更加完美，我们可以这样考虑：实际上b的数据可以算是一个冗余数据，即通过a和x的数据可以唯一确定b的数据，此时我们省去那个数组b，就能用类似的方法来解决这个问题了，还是设置标点i和j，看看a[i]+a[j]的值和x比较，相等则退出，大于x则j--(减小a[j])，小于x则i++(增大a[i])。这样就去除了那个附加空间了！^_^

实现代码：

#include<stdio.h>
#include<algorithm>
const int MAXN=5000;
int i,j,n,x,a[MAXN];
int main()
{
scanf("%d",&n);
scanf("%d",&x);
for (i=0;i<n;i++)
   scanf("%d",&a[i]);
std::sort(a,a+n);//我比较懒，为了说明主要问题这里用了算法库里自带的排序^_^
i=0;j=n-1;
while (i<j)
{
   if (a[i]+a[j]==x) break;
   if (a[i]+a[j]>x) j--;
   else i++;
}
if (i!=j) printf("%d %d\n",a[i],a[j]);
else printf("No Answer!\n");
return 0;
}

输入数据：

12
7
2 6 4 8 4 2 10 11 9 6 8 3

输出数据：

3 4

输入数据：

5

5

2 2 2 2 2

输出数据：

No Answer！

说明：输入和输出数据只是参考，我还测试了几组随机数据，效果还好！