【转】 在数组中查找和为定值的两个数

输入一个已经按升序排序过的数组和一个数字，在数组中查找两个数，使得它们的和正好是输入的那个数字。要求时间复杂度是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;
}