C-在排序数组中查找和为给定值的若干数字?

C-在排序数组中查找和为给定值的若干数字?

夜无邪 发布于 2017-03-05 字数 0 浏览 1177 回复 2

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(2

泛泛之交 2017-09-20 2 楼

给定数值 N, 数组已经排序,在以上算法基础上加一些限定条件做优化。
1:首先定位N/2所处的大约位置 i,枚举集合的时候,忽略含有大于等于两个>i位置的集合
2:比N小的前半部分进入原问题算法,后部分不需要考虑
3:由小到大加和,大于N/2且还有元素剩余的时候,直接抛弃当前集合

归属感 2017-03-14 1 楼

这个需要大家验证一下,希望高手给与指正,这个是网上程序员面试题精选100题中的一个答案,应该可以帮到你:

参考代码:

///////////////////////////////////////////////////////////////////////
// Find two numbers with a sum in a sorted array
// Output: ture is found such two numbers, otherwise false
///////////////////////////////////////////////////////////////////////
bool FindTwoNumbersWithSum
(
int data[], // a sorted array
unsigned int length, // the length of the sorted array
int sum, // the sum
int& num1, // the first number, output
int& num2 // the second number, output
)
{

bool found = false;
if(length < 1)
return found;

int ahead = length - 1;
int behind = 0;

while(ahead > behind)
{
long long curSum = data[ahead] + data[behind];

// if the sum of two numbers is equal to the input
// we have found them
if(curSum == sum)
{
num1 = data[behind];
num2 = data[ahead];
found = true;
break;
}
// if the sum of two numbers is greater than the input
// decrease the greater number
else if(curSum > sum)
ahead --;
// if the sum of two numbers is less than the input
// increase the less number
else
behind ++;
}

return found;
}

来自:http://zhedahht.blog.163.com/blog/static/2541117420072143251809/