JZ42-和为S的两个数字(双指针、数组)

描述

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

返回值描述：

对应每个测试案例，输出两个数，小的先输出。

示例1

输入：

[1,2,4,7,11,15],15

返回值：

[4,11]

解题思路

和41差不多，双指针一个指向开头一个指向末尾，向中间靠拢

但是这题隐藏了一个条件

对于乘积最小的两个数来说，两个数相差越大它们的乘积反而越小，故而第一个满足条件的数组就是结果

证明:

a+b=s
a=s-b
a*b=b(s-b)=-(b-s/2)^2+s^2/4
所以当b趋近s/2即a趋近于b时乘积最大
反证得结论

代码

function FindNumbersWithSum(array, sum)
{
    // write code here
    let len = array.length;
    let left = 0;
    let right = len-1;
    let arr = [];
    while(left<right){
        if(array[left]+array[right]>sum){
            right--;
        }else if(array[left]+array[right]===sum){
            let temp = []; //用临时数组保存
            temp.push(array[left]);
            temp.push(array[right]);
            arr.push(temp);
            right--;
        }else{
            left++;
        }
    }
    if(arr.length===0){
        return arr; //如果找不到返回空数组
    }
    return arr[0] //否则返回第一组满足的
}
module.exports = {
    FindNumbersWithSum : FindNumbersWithSum
};

这题的隐藏条件可以省掉许多步骤，之前自己写的时候还专门存储了乘积再进行排序截取，还是需要多观察隐藏条件

弃用

function FindNumbersWithSum(array, sum)
{
    // write code here
    let len = array.length;
    let left = 0
    let right = len - 1;
    let arr = [];
    while (left < right) {  //双指针
        let total = array[left] + array[right];
        if (total > sum) {
            right--;
        } else if (total == sum) {
            let temp = [];
            temp.push(array[left]);
            temp.push(array[right])
            arr.push(temp);
            right--;
        } else if (total < sum) {
            left++;
        }
    }
    // console.log(arr)
    if (arr.length == 0) {  //无法满足则退出
        return arr
    }
    for (let i = 0; i < arr.length; i++) {  //计算乘积
        arr[i][2] = arr[i][0] * arr[i][1];
    }
    let min = arr[0][2];
    let ar = [];
    ar.push(arr[0]);
    for (let j = 0; j < arr.length; j++) {  //排序
        if (arr[j][2] < min) {
            ar.pop();
            min = arr[j][2];
            ar.push(arr[j]);
        }
    }

    return ar[0].slice(0, 2)  //返回对应的两个数
}