标题: [Microsoft面试]题目：输入一个已经按升序排序过的数组和一个数字， 在数组中查找两个数，使得它们的和正好是输入的那个数字。 要求时间复杂度是O(n)。 [打印本页] 作者: 陈荣莲 时间: 2013-8-16 10:52 标题: [Microsoft面试]题目：输入一个已经按升序排序过的数组和一个数字， 在数组中查找两个数，使得它们的和正好是输入的那个数字。 要求时间复杂度是O(n)。 如果有多对数字的和等于输入的数字，输出任意一对即可。例如输入数组1、2、4、7、11、15 和数字15。由于4+11=15，因此输出4 和11。作者: 秦静静 时间: 2013-8-16 11:10
Use twocursors. One at front and the other at the end. Keep track of the sum by movingthe 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, %d\n”, *f,*e);}