和为S的两个数字O(logn * logn)解法

题目描述

输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。

输出描述:

对应每个测试案例，输出两个数，小的先输出。

解法

1. 穷举：

对所有数据对都查找一遍
时间复杂度：O(n^2)

2. 哈希表：

建立哈希表查找 k-array[i]
时间复杂度：O(n)
空间复杂度：O(n)

3. 双指针：

时间复杂度：O(n),设置左右指针，向中间搜索合适的值，直到指针相遇
空间复杂度：O(1)

4. 双指针 + 二分查找：

时间复杂度：O(logn * logn)
空间复杂度：O(1)
前三种方法实现上难度为0，方法4需要对二分查找比较熟练。设置左右指针，每次向中间搜索时用二分法查找合适的值，没有合适的值就定位在闭边界位置。后台的测试用例应该都很短，这种情况下时间效率不如第一种方法。如果数组长度是1000，时间效率可提升10倍（10 = 2^10/(10 * 10))。

代码

class Solution {
public:
    vector<int> FindNumbersWithSum(vector<int> array,int sum) {
            vector<int> result;
    if (!array.size())
        return result;
    int le = 0, ri = array.size() - 1;
    int l, r, m;
    int t;
    while (le < ri - 1) {
        if (array[le] + array[ri] == sum) {
            result = {array[le], array[ri]};
            return result;
        }
        else if (array[le] + array[ri] > sum) {
            t = sum - array[le];
            l = le + 1;
            r = ri;
            while (l < r) {
                m = (l + r) / 2;
                if (array[m] == t) {
                    result = {array[le], array[m]};
                    return result;
                }
                else if (array[m] > t)
                    r = m;
                else
                    l = m;
                if (l >= r - 1)
                    break;
            }
            ri = l;
        }
        else {
            t = sum - array[ri];
            l = le;
            r = ri - 1;
            while (l < r) {
                m = (l + r + 1) / 2;
                if (array[m] == t) {
                    result = {array[m], array[ri]};
                    return result;
                }
                else if (array[m] > t)
                    r = m;
                else
                    l = m;
                if (l >= r - 1)
                    break;
            }
            le = r;
        }
    }
    return result;

    }
};