剑指offer编程题—和为S的两个数字

题目描述
输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。
输出描述:
对应每个测试案例，输出两个数，小的先输出。

解题思路
因为给定的数组是递增有序的，所以这里可以使用双指针技术，两个指针分别指向数组的首和尾，求解过程中两个指针分别向中间移动，具体操作步骤如下：

1. 初始化指针lp和rp分别指向数组的首和尾；
2. 如果array[lp]+array[rp]==sum，说明是正解，因为lp是自左向右移动的，所以第一次求出的解肯定是所有可能解里面乘积最下的解，又题目并没有要求求出所有解，因此这里可以直接返回答案，求解结束；
3. 如果array[lp]+array[rp]<sum，说明和太小，需要增大，所以++lp；
4. 如果array[lp]+array[rp]>sum，说明和太大，需要减小，所以--rp;

class Solution {
public:
    vector<int> FindNumbersWithSum(vector<int> array,int sum) {
        vector<int> res;
        if(array.size()<2) return res;
        int lp=0;
        int rp=array.size()-1;
        int tmpsum=0;
        while(lp<rp && array[lp]<=sum/2 && array[rp]>=sum/2){
            tmpsum =array[lp]+array[rp];
            if(tmpsum == sum){
                res.push_back(array[lp]);
                res.push_back(array[rp]);
                break;
            }
            else if(tmpsum<sum){
                ++lp;
            }
            else{
                --rp;
            }
        }
        return res;
    }
};

注意循环跳出的条件。