现在的位置: 首页 > 综合 > 正文

查找两数之和等于给定值

2013年05月24日 ⁄ 综合 ⁄ 共 835字 ⁄ 字号 评论关闭

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

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

#include <stdio.h>

//假设此数组是按照升序排列
void find_two_numbers(int array[], int len, int value)
{
    int sum, small_index, big_index;
    
    small_index = 0;        //small_index初始化指向数组第一个数
    big_index = len - 1;    //big_index初始化指向数组最后一个数
    sum = 0;                //sum初始化为0
    
    while(small_index < big_index)      //当big_index >= small_index是退出循环
    {
        sum = array[small_index] + array[big_index];
        if(sum > value)                 //若此二数之和大于value,则需要将big_index指向更小一些的数
        {
            big_index --;
        }else if(sum < value)           //若此二数之和小于value,则需要将small_index指向更大一些的数     
        {
            small_index ++;
        }else
        {
            printf("%d + %d = %d\n",array[small_index],array[big_index],value);
            //return ;                  //若只需要一组数,则此时就可以结束程序
            big_index --;
            small_index ++;             //更改两个index值,继续查找其它满足条件的数
        }
    }
}

int main()
{
    int array[] = {-1,0,1,2,4,7,8,11,15};
    int len = 9;
    int value = 15;
    
    find_two_numbers(array, len, value);
    
    return 0;
}

抱歉!评论已关闭.