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

题目：和为S的两个数字

描述：输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，返回两个数的乘积最小的，如果无法找出这样的数字，返回一个空数组即可。

返回值描述：对应每个测试案例，输出两个数，小的先输出。

一种方法为暴力破解法：

思路分析：在暴力破解中，利用双重遍历，首先遍历位置i的数字，其次遍历j= i+1对应的数字，通过将两个数字与Sum的大小进行比较。

（1）若a[i] + a[j] == sum，则将两个数字进行保存，将已保存的数据与之进行比较，比较完成后保存最小值。

（2）若a[i] + a[j] > sum，则需要将i-1后再次判断。

（3）若a[i] + a[j] < sum，则需要将j+1后再次判断。

具体思路描述：当递增序列为[1,2,4,7,11,15]，数字S为15时，进行以下分析：

首先将i和j的指针分别指向数组的位置0（数字1）与位置1（数字2），判断输出的和为3，执行上述第（3）条语句。

……

以此类推，j执行完一轮后得到的值大于Sum，将执行上述第（2）条语句。

判断完成后，继续进行与Sum值之间的判断。执行上述语句（3）。

……

j再次执行完一轮后得到的值大于Sum，将执行上述第（2）条语句。

当指针执行到上述情况时，符合条件，将两个数字保存到容器当中，以此类推进行判断。

具体程序如下所示：

class Solution {
public:
vectorFindNumbersWithSum(vectorarray,int sum) {
    int num = array.size();
    vector res;//该容器为最终存储的值
    if(num < 2){ return res; } if(sum > (array[num - 1] + array[num - 2]))//该情况属于不存在任何一组
        return res;
    for(int i = 0;i < num - 1;i++){ 
    for(int j = i + 1;j < num;j++){ 
        int num1,num2; 
        if(sum == (array[i] + array[j])){ 
            num1 = array[i]; num2 = array[j]; 
            if(res.size()==0){ 
                res.push_back(num1); 
                res.push_back(num2); } 
            else if(num1 * num2 < res[0]*res[1]){ 
                res[0]=num1; 
                res[1]=num2; 
            } 
        break; 
        } 
    } 
} 
return res; 
    } 
};

思路分析：因为题目中给定数组为递增排序，所以可以给定两个指针为i和j，其中i指针为头指针，j指针为尾指针，通过判断两个指针的和来判断最终答案是否符合要求。

主要分为以下几种情况：
（1）若a[i] + a[j] == sum，则符合条件。（题目中要求输出的两个数在满足条件的情况下乘积最小，递增数组在已经排序完整的情况下，最外层的两个数字乘积最小）

（4）若a[i] + a[j] > sum，则需要将j自减1进行再次判断。

（5）若a[i] + a[j] < sum, 则需要将i自增1进行再次判断

具体思路描述：当递增序列为[1,2,4,7,11,15]，数字S为15时，进行以下分析：

首先将指针i，j分别指向数组的首尾端，进行第一次判断，判断结果和为16，结果值不等于数字S的值，执行上述语句（2）。

判断两个数相加和为12，执行上述语句（3）。

判断两个数相加和为13，执行语句（3）。

判断两个数相加的结果为15，执行语句（1），输出最终结果为[4,11]。

具体java程序如下所示：

import java.util.ArrayList;
public class Solution {
public ArrayListFindNumbersWithSum(int [] array,int sum) {
    ArrayListlist = new ArrayList();
    int length = array.length;//数组的长度
    int i = 0;//首
    int j = length - 1;//尾
    while(i < j){ if(array[i] + array[j] == sum){ list.add(array[i]); list.add(array[j]); break; } if(array[i] + array[j] > sum)
            j--;
        if(array[i] + array[j] < sum) i++; } return list; } }

C++版本为：

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

两种语言的时间复杂度均为O(n)。