题目:给定数组A,大小为n,现给定数X,判断A中是否存在两数之和等于X
思路一:
1,先采用归并排序对这个数组排序,
2,然后寻找相邻<k,i>的两数之和sum,找到恰好sum>x的位置,如果sum=x则返回true,
3,找到位置后,保持i不变,从k处向前遍历,直到找到A[k]+A[i]等于x,并返回TRUE,如果找不到,则返回false。
论证步骤3:当前找到的位置恰好A[k]+A[i]>x,且前一位置的sum<x;
所以A[i]前面的数(不包括A[i])无论取哪两个数都不可能使和等于x,只能小于x
对位置k向前寻找时,当寻找到A[k]+A[i]=sum,返回true;当寻找到sum<x时,令k=i,跳出对k的循环,继续寻找
当所有的路径寻找完之后,返回false,没找到
代码如下:
public boolean ExitSumX(int A[],int x)
{
//归并排序
MessSort(A); int k=0;
for(int i=1;i<A.length;i++)
{
if(i!=k)
{
if(A[k]+A[i]==x)
return true;
else if(A[k]+A[i]<x)
k=i;
else
{
while(k>0)
{
k--;
if(A[k]+A[i]==x)
return true;
else if(A[k]+A[i]<x)
{ k=i;break; };
}
}
}
}
return false;
}
算法分析:归并排序时间为:O(nlgn),寻找算法时间复杂度为O(n2),算法整体时间复杂度为:O(n2),可见算法不算太好
思路二:
这种算法时间复杂度为O(nlgn),思路来自 算法导论