在排序数组中查找和为给定值的两个数字

时间：2009-07-21 来源：ubuntuer

输入一个已经按升序排序过的数组和一个数字，在数组中查找两个数，使得它们的和正好是输入的那个数字。要求时间复杂度是O(n)。如果有多对数字的和等于输入的数字，输出任意一对即可。例如输入数组1、2、4、7、11、15和数字15。由于4+11=15，因此输出4和11。这题就比较简单了。当然肯定不是先在数组中固定一个数字，再依次判断数组中剩下的n-1个数字与它的和是不是等于输入的数字。可惜这种思路需要的时间复杂度是O(n*n)。最初我们找到数组的第一个数字和最后一个数字。当两个数字的和大于输入的数字时，把较大的数字往前移动；当两个数字的和小于数字时，把较小的数字往后移动；当相等时，打完收工。这样扫描的顺序是从数组的两端向数组的中间扫描。

#include <stdio.h>
#include <stdlib.h>

#define N 6
void find_sum(int A[], int sum)
{
  int i = 0;
  int j = N-1;
  int k;

while( i!=j)
{
  k = A[i]+A[j];
  if(k == sum)
   {
     printf("%d + %d = %d\n",A[i],A[j],sum);
     return;
   }
  else if(k<sum)
   i++;
  else
   j--;
}

printf("sorry not found\n");
}
int main(int argc, char *argv[])
{
  int A[] = {1, 2, 4, 7, 11, 15};
  int sum = 15;

  find_sum(A, sum);
  system("PAUSE");
  return 0;
}