第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; }