剑指offer系列——42.和为S的两个数字

Q：输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。
T：
这个题承接上一个题目，使用双指针法。因为题目中有说，输出两个数乘积最小的，而设\(S=2n,(n+k)(n-k)=n^2-k^2<=n^2\)，k越大，乘积越小，因此可以设置第一个指针在头，第二个指针在尾，左右夹逼法。碰到第一个满足条件即可。

    vector<int> FindNumbersWithSum(vector<int> array, int sum) {
        vector<int> result;
        if (array.empty())
            return result;
        int index1 = 0;
        int index2 = array.size() - 1;
        while (index1 <= index2) {
            if (array[index1] + array[index2] == sum)
                break;
            else if (array[index1] + array[index2] < sum) {
                index1++;
            } else
                index2--;
        }
        if (array[index1] + array[index2] == sum) {
            result.push_back(array[index1]);
            result.push_back(array[index2]);
        }
        return result;
    }

剑指offer系列——42.和为S的两个数字

原文：https://www.cnblogs.com/xym4869/p/12335937.html