【刷算法】和为S的两个数字

题目描述

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

解题思路

数组是递增的，且给的数字S是固定的，那就可以用夹逼法。 两个指针left和right从数组的两端开始，要是left和right指向的数字之和大于S，说明right得向左移动一下，因为right的左边是比它小的数字；要是left的right指向的数字之和小于S，说明left得向 右边移动一下，因为left的右边是比它大的数字。left和right碰头了说明该结束了。

代码实现

function FindNumbersWithSum(array, sum)
{
    if(!array || array.length < 2 || sum === 0)
        return [];
    var left = 0;
    var right = array.length-1;
    var res = [];
    while(left !== right) {
        var curSum = array[left]+array[right];
        if(curSum === sum){
            res.push(array[left]);
            res.push( array[right]);
            break;
        }
        else if(curSum > sum)
            right--;
        else 
            left++
    }
    return res;
}
复制代码