[8]求数组中两个和为定值的元素

【题目】输入一个已经按升序排序过的数组和一个数字，在数组中查找两个数，使得它们的和正好是输入的那个数字。要求时间复杂度是O(n)。如果有多对数字的和等于输入的数字，输出任意一对即可，例如输入数组1、2、4、7、11、15和数字 15。由于4+11=15，因此输出4 和11。 【思路】升序数组，按照头尾元素之和进行判断，如果大于和值，尾前移一位，如果小于和值头后移一位。

【代码】

//By proing [http://blog.csdn.net/proing] #include "stdafx.h" #include <iostream> using namespace std; void FindNum(int *arr,int n, int sum) { int begin = 0; int end = n-1; while(begin < end) { if(sum == arr[begin]+arr[end]) { cout<<"The number is "<<arr[begin]<<" and "<<arr[end]<<endl; return; } else if (sum > arr[begin]+arr[end]) begin++; else end--; } cout<<"Not Find the correct number!"<<endl; }