和为S的两个数字

题目描述

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

问题分析

结合和为S的连续正数序列思路，选用两个索引，一个从头开始，另一个从尾部开始。
如果两个数字和为S且乘积最小，那么这两个数的差是最大的，才能保证是乘积最小。
所以按从头部和尾部分别搜索，第一次出现和为S的数字即为乘积最小的数字。

解题思路1

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

    }
    return result ;
    }
};