和为S的两个数字
题目描述
输入一个递增排序的数组和一个数字S,在数组中查找两个数,使得他们的和正好是S,如果有多对数字的和等于S,输出两个数的乘积最小的。
输出描述:
对应每个测试案例,输出两个数,小的先输出。
联动
和为s的连续序列
思路:因为要查找两个数字,使得他们的和为S,而且输出的时候,乘积最小的输出,所以依然采用双指针的方式来做。
1.双指针,slow=0,high=array.length-1;(注意这里区分,连续和为s的序列,一个high指向2,一个指向数组末尾)
2.健壮性:数组长度小于2,返回[]
3.循环开始的条件:slow<high
4.不断比较当前和与sum和current(注意:这里的current=array[slow]+array[high]一定要放在while循环的里面,如果放在外面,current永远都是array[0]+array[array.length-1]。自己第一次写的时候,就是这没注意,一直报错。)
4.1.current<sum,slow++;
4.2.current>sum,high--;
4.3.current==sum,result.push(array[slow],array[high])
function FindNumbersWithSum(array, sum)
{
// write code here
if(array.length<2) return [];
var slow=0;var high = array.length-1;var list = [];
while(slow<high){
var current = array[slow]+array[high];
if(current<sum){
slow++
}else if(current>sum){
high--;
}else if(current==sum){
list.push(array[slow]);
list.push(array[high]);
break;
}
}
return list;
}
京公网安备 11010502036488号