题解 | #和为S的两个数字#

题目：
描述
输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，返回两个数的乘积最小的，如果无法找出这样的数字，返回一个空数组即可。
返回值描述：
对应每个测试案例，输出两个数，小的先输出。
输入：[1,2,4,7,11,15],15
返回值：[4,11]

方法一：暴力求解法
第一步：首先对第一个元素及其后的所有元素进行遍历，找到所有的符合要求的两个数将其放在返回的数组中。
第二步：在所有符合要求的数组中找到两个数乘积最小的那一对，首先数组如果为空，则直接将第一组符合要求的输入进去，如果出现了第二组，就将第二组的乘积与第一组进行比较，如果第一组的大于第二组的乘积，就将原数组的元素删除，入驻新的元素。

vector FindNumbersWithSum(vector array,int sum) {
       vector A;
       if(array.empty())
       {
           return A;
       }
       for(int i = 0; i < array.size(); i++)
       {
           for (int j = i+1; j < array.size(); j++)
           {
               if(array[i] + array[j] == sum)
               {
                   if(A.empty())
                   {
                       A.push_back(array[i]);
                       A.push_back(array[j]);
                   }
                   else{
                       if(array[i]*array[j] < A[0]*A[1])
                       {
                           A.clear();
                           A.push_back(array[i]);
                           A.push_back(array[j]);
                       }
                   }
               }
           }
       }
        return A;

复杂度分析：
时间复杂度O(n^2)
空间复杂度：O(1)

下面两种解法参考官方答案
方法二：hash表方法
要求a + b = sum, 如果已知a， 那么b = sum - a
所以可以先将b添加入哈希中，然后遍历一遍数组设为a， 在哈希中寻找是否存在sum-a，然后再更新乘积最小值
这个方法涉及到很多新的知识点，比如，mp.find(); pair<int>p; pair变量的调用方法，p.first，p.second;</int>

方法三：双指针，就很妙
因为数组是有序的，所以可以使用双指针，指向数组的首尾，具体步骤如下：

1. 初始化：指针i指向数组首部，指针j指向数组尾部。
2. 如果arr[i]+arr[j]==sum，说明是可能解
3. 否则如果arr[i] + arr[j] > sum, 说明和太大，所以j--
4. 否则如果arr[i] + arr[j] < sum, 说明和太小，所以i++