题目描述

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

思路

双指针思想
既然是递增数组，可以想到双指针思想
定义两个指针(i为数组头，j为数组尾)
小的话，左指针右移，大的话，右指针左移；
循环结束条件就是i超过了j
如果出现多对数字的和等于S，一开始我是定义了一个二维数字，存放所有满足条件的序列，之后再进行比较，返回乘积最小的那个，但是本地通过了，牛客上段错误(还没发现问题)

后来看讨论区发现，一个定理，和相等时，两个数相差越大则乘积越小，证明如下：
已知：x+y=C
x+y=C（C是常数），xy的大小。不妨设y>=x，y-x=d>=0，即y=x+d, 2x+d=C, x=(C-d)/2, xy=x(x+d)=(C-d)(C+d)/4=(C^2-d^2)/4，也就是xy是一个关于变量d的二次函数，对称轴是y轴，开口向下。d是>=0的，d越大, xy也就越小。
#代码

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

错误代码：

class Solution {
public:
    vector<int> FindNumbersWithSum(vector<int> array,int sum) {

        vector<int> seq;
        vector<vector<int>> res;//如果存在多对数字的和等于S，那就先都存进res中
        int i=0,j=array.size()-1;//i,j分别为左右指针
        int minmul=1;//保存最小乘积
        int pos=0;//保存最小乘积序列的位置
        while(i<j)//求和为S的数
        {
            if(array[i]+array[j]==sum)
            {
                seq.push_back(array[i]);
                seq.push_back(array[j]);
                res.push_back(seq);
                seq.clear();
                i++;
            }
            else if(array[i]+array[j]<sum)//如果小的话，左指针右移
            {
                i++;
            }
            else         //如果大的话，右指针左移
                j--;
        }
        if(res.size()==1)
            return res[0];
        else
        {
            minmul=res[0][0]*res[0][1];//初始化乘积
            pos=0;//初始化乘积的位置(乘积最小的序列的位置)
            for(int i=1;i<res.size();i++)
            {
                if(res[i][0]*res[i][1]<minmul)
                {
                    minmul=res[i][0]*res[i][1];
                    pos=i;
                }
            }
            return res[pos];
        }
    }
};