14. 排序数组中找和为n的两数

题目：输入一个已经按升序排序过的数组和一个数字，
在数组中查找两个数，使得它们的和正好是输入的那个数字。
要求时间复杂度是O(n)。如果有多对数字的和等于输入的数字，输出任意一对即可。

例如输入数组1、2、4、7、11、15 和数字15。由于4+11=15，因此输出4 和11。

HANDWRITING:

void search(int *a, int size, int n) {
	int s = 0, e = size - 1, sum;
	while (s < e) {
		sum = a[s] + a[e];
		if (sum == n) cout<<a[s]<<" "<<a[e]<<endl;
		else if (sum < n) ++s;
		else --e;
	}
}

ANSWER FROM:http://blog.csdn.net/v_july_v/article/details/6870251
Use two cursors. One at front and the other at the end. Keep track of the sum by moving the cursors.

void find2Number(int a[], int n, int dest) {
  int *f = a, *e=a+n-1;
  int sum = *f + *e;
  while (sum != dest && f < e) {
    if (sum < dest) sum = *(++f);
    else sum = *(--e);
  }
  if (sum == dest) printf(“%d, %dn”, *f, *e);
}

最后

以上就是笑点低星星为你收集整理的14. 排序数组中找和为n的两数的全部内容，希望文章能够帮你解决14. 排序数组中找和为n的两数所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。