题目描述
输入一个递增排序的数组和一个数字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; }
//