算法导论2.3-7

[算法导论2.3-7]
转自：http://www.cnblogs.com/xuxu8511/archive/2012/08/26/2657685.html
方法1、
先排序，然后比较：

int i=0,

j=n-1;
int b=0;
while (i<j)
{
    int k=s[i]+s[j];
    if (k==x) b=1,break;
    else if (k<x) i++;
    else j--;
}
if (b) printf("Y\n");
else printf("N\n");

nlgn+n=nlgn,即可以在规定时间内完成。

方法2、
先排序，时间复杂度为：o(nlgn)
S={y,y<x,y∈S}，有序数组。
S'={z:z=x-y,y∈S},显然S'也是一个有序数组。
然后，合并S、S’ 数组，如果存在两个连续的相等值，也就是y1,y1,...,y2,y2 且y1+y2 = x，那么集合S中就存在两个数的和为X。
那么，就存在y1+y2 = x，满足条件。
为什么要存在两个连续的相等值呢？
-------因为数是对称的，如果存在y1，使得y1=x-y2,那么也有y2 =x-y1存在。
o(nlgn) +o(n) = o(nlgn)

同样道理，找三个数之和也可以在n^{2时间内完成。sum=a[i]+b[i]+c[i];等价找两个数其和为s=sum-a[i];共有n个，每个查找为线性时间n；nlgn+n}2=n^2。