主题:[讨论]在有序整数组中用O(n)算法求是否有两数和为X,谁有较好的思想的?
令A[1..n]是一个n个整数和已排序的数组,x是整数。请设计一个O(n)时间的算法来确定在A中是否存在这样的两个数,它们的和恰好是X。
还有,如果要求证是否存在这样的三个数它们的和恰好是X的算法。
谁对这两个问题有较好的思想的,可以说一说不?
对于验证两个数的,我的想法是这样的:
bool FindX::get2Result(int *data,int size, int x, int *r1, int *r2)
{
int i,j,n;
for(j=size-1;j>=0;j--)
{
if(data[j]<x)
break;
}
n=j;
i=0;
while(i<=n&&j>=0)
{
if(data[i]+data[j]>x)
{
j--;
}
else if(data[i]+data[j]<x)
{
i++;
}
else
{
*r1=i;
*r2=j;
return true;
}
}
return false;
}
但没有证明过这样是否正确,望有高人指点一下,any answer will be appreciated~~[em1]
还有,如果要求证是否存在这样的三个数它们的和恰好是X的算法。
谁对这两个问题有较好的思想的,可以说一说不?
对于验证两个数的,我的想法是这样的:
bool FindX::get2Result(int *data,int size, int x, int *r1, int *r2)
{
int i,j,n;
for(j=size-1;j>=0;j--)
{
if(data[j]<x)
break;
}
n=j;
i=0;
while(i<=n&&j>=0)
{
if(data[i]+data[j]>x)
{
j--;
}
else if(data[i]+data[j]<x)
{
i++;
}
else
{
*r1=i;
*r2=j;
return true;
}
}
return false;
}
但没有证明过这样是否正确,望有高人指点一下,any answer will be appreciated~~[em1]