博客

微软面试题，难度系数低，题目描述如下：

题目：输入一个已经按升序排序过的数组和一个数字，

在数组中查找两个数，使得它们的和正好是输入的那个数字。

要求时间复杂度是O(n)。如果有多对数字的和等于输入的数字，输出任意一对即可。

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

逻辑分析：

1、针对一个元素相对少的数组，第一想法一般是枚举，两层循环可以遍历所有的两个元素和，时间复杂度O(n^2)，显然笨拙又不满足要求。

void find2Number(int a[], int n, int dest)
{
    int i,j;
    for(i=0; i<n; i++)
    {
        for(j=i+1; j<n; j++)
        {
            if(dest == a[i] + a[j])
            {
                printf("%d,%d\n",a[i],a[j]);
                return ;
            }
        }
    }
}

2、题目要求时间复杂度为线性，即O(n)，那么，如果每个元素我们只遍历一遍，或者至多遍历一次，就可以满足题目要求。既然数组是有序的，那么我们完全可以在数组的头部和尾部放置两个指针front，rear，首先比较*front和*rear的和与dest，若dest小，则后移front，若dest大，则前移rear，结束条件显然是sum==dest || front == rear。

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) + *e;
        else
            sum = *(--e) + *f;
    }
    if (sum == dest)
        printf("%d, %d\n", *f, *e);
}