2015远景能源校园招聘 笔试题（同济大学站）

对于一个给定的降序序列，给定一个N。在数组中找出两个数，使他们的和等于给定数。要求时间复杂度是o(n). 

 

bool FindSumElements(int array[], int length, int sum, int *elem1, int *elem2)
{
    if(length == 0)
    {
        return false;
    }
                                                                                                                                    int tempSum = 0;
    //记录elem1和elem2的值分别在数组中下标序号是多少
    //elem1从第一个元素开始，elem2从最后一个元素开始                                                                                                                                                                                                                      int head = 0;
    int tail = length-1;                                                                                                            while(head < tail)
    {
        tempSum = array[head] + array[tail];
        if(tempSum == sum)
        {
            *elem1 = array[head];
            *elem2 = array[tail];
            return true;
        }else if(tempSum > sum)
        {
            --tail;
        }else
        {
            ++head;
        }
    }
 
    return false;
}

思路：

因为数组是按升序排序过的，所有后面的值一定比前面的值大。

设两个变量elem1和elem2，elem1从数组第一个数开始向后走，elem2从数组最后一个数开始向前走。

求两个变量的和，与给定数字作比较：

当和大于给定数字时，elem2向前走一步，继续比较；

当和小于给定数字时，elem1向后走一步，继续比较；

当和等于给定数字时，返回当前两个变量值，退出查找。