和为S的两个数字

---

题目描述

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

输出描述：

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

解题思路

解题思路和上一次，求递增数组连续数字的和为S的思路一样。

• 通过两个指针来实现。一个指针pleft，指向最左元素；另一个指针pright，指向最右边元素；
• 计算两个指针指向元素的和，判断当前和与指定和S的大小；
• 若当前和 < S，则将左指针向左移动一位；
• 若当前和 == S，则将两指针指向的元素压入输出容器中；
• 若当前和 > S，则将右指针向右移动一位；

双指针左右遍历递增序列时，最开始满足和为S的即为乘积最小的两个数。

证明:

假设 a < b，且存在；

a + b = s内层的两个数

(a - n) + (b + m) = s 外层的两个数

(a - n) + (b + m) = a + b ==> m = n;

(a - n)(b + m) = ab + am -bn - nm = ab - (b - a)m - m^2 < ab

即可证明。

代码

class Solution
{
public:
    vector<int> FindNumbersWithSum(vector<int> array,int sum)
    {
        vector<int> result;
        if (array.size() == 0)
            return result;
        
        int pleft = 0, pright = array.size() - 1;
        while (pleft < pright)
        {
            int cursum = array[pleft] + array[pright];
            if (cursum < sum)
                pleft++;
            if (cursum == sum)
            {
                result.push_back(array[pleft]);
                result.push_back(array[pright]);
                return result;
            }
            if (cursum > sum)
                pright--;
        }
        return result;
    }
};