【转】 在数组中查找和为定值的两个数
输入一个已经按升序排序过的数组和一个数字，在数组中查找两个数，使得它们的和正好是输入的那个数字。要求时间复杂度是O(n)。如果有多对数字的和等于输入的数字，输出任意一对即可。
例如输入数组1、2、4、7、11、15和数字15。由于4+11=15，因此输出4和11。
设和为 sum，数组为a
分析：
（1）遍历一遍数组，当前遍历到a[i]。由于生序排列，可以二分查询sum-a[i]是否在a中的复杂度为O(lgn)，整个算法复杂度为O(nlgn)，不合题意。
（2）对于每一个数a[i]，关键问题是查询sum-a[i]是否在a中。题目中升序排列这个条件还有一个性质，
对于j>i --> a[j] > a[i] --> sum-a[i] < sum-a[j]
这说明了，我们在查询完sum-a[i]是否在数组中后（假设a[j]<sum-a[i], a[j+1]>=sum-a[j]），查询sum-a[i+1]可以缩小到[i+1, j]这个范围。
#include <iostream>
using namespace std;
bool find(int* a, int len, int sum, int& x) {
int right = len-1;
for(int i = 0; i <= right; i++) {
x = sum-a[i];
while(right >= 0 && a[right] > x) right --;
if(right == -1) break;
if(a[right] == x) {
return true;
}
}
return false;
}
int main() {
int a[6] = {1, 2, 4, 7, 11, 15};
int x, sum = 15;
if(find(a, 6, sum, x)) {
cout << sum-x << " " << x << endl;
}
return 0;
}