編程算法 - 和為s的兩個數字 代碼(C)

編程算法 - 和為s的兩個數字 代碼(C)

和為s的兩個數字 代碼(C)

題目: 輸入一個遞增排序的數組和一個數字s, 在數組中查找兩個數, 使得它們的和正好是s.

如果有多對數字的和等於s, 輸出任意一對即可.

排序數組, 則可以從兩端(即最大值, 最小值)開始進行查找, 當和大於時, 則減少前端, 當和小於時, 則遞增尾端.

時間復雜度O(n).

代碼:

/*
 * main.cpp
 *
 *  Created on: 2014.6.12
 *      Author: Spike
 */

/*eclipse cdt, gcc 4.8.1*/

#include 
#include 
#include 

bool FindNumbersWithSum(int data[], int length, int sum, int* num1, int* num2)
{
	bool found = false;
	if (length<1 || num1==NULL || num2 == NULL)
		return found;
	int ahead = length-1;
	int behind = 0;

	while (ahead > behind) {
		long curSum = data[ahead] + data[behind];
		if (curSum == sum) {
			*num1 = data[behind];
			*num2 = data[ahead];
			found = true;
			break;
		} else if (curSum < sum)
			++behind;
		else
			--ahead;
	}
	return found;
}

int main(void)
{
	int data[] = {1, 2, 4, 7, 11, 15};
	int num1, num2;
	if (!FindNumbersWithSum(data, 6, 15,  &num1, &num2))
		printf(Error
);
	printf(num1 = %d num2 = %d
, num1, num2);
}

num1 = 4 num2 = 11