題目
現(xiàn)有一個遞增排序的數(shù)組和一個數(shù)字S氓皱，在數(shù)組中查找兩個數(shù)滞造，是的他們的和正好是S续室，如果有多對數(shù)字的和等于S栋烤，輸出兩個數(shù)的乘積最小的谒养。
求解思路
思路一
開始拿到題目，最先想到的是兩個for循環(huán)明郭，將之遍歷买窟，可得出答案。
但是薯定，如果這個數(shù)組很大始绍，n^2的時間復雜度顯然不是理想的做法。
思路二
在使用文字描述之前话侄，先看下下面的思路拆解步驟吧亏推，應該比起文字來會更容易明白。
思路拆解
var arr = [1,3,4,5,6,7,8,9,10]
var sum = 12;
1+10 < 12
3+10 > 12
3+9 == 12;
get 3 9
4+8=12
get 4 8
5+7=12
get 5 7
文字講解
對arr進行頭尾向中間遍歷的方式年堆。
1+10<12說明相加的數(shù)小了吞杭，所以頭部向中間進一步。
3+10>12說明相加的數(shù)大了变丧，所以尾部向中間進一步芽狗。
以此類推，直到頭尾的指向都停留在中間痒蓬，該遍歷結束童擎。
上代碼
function FindNumbersWithSum(array, sum) {
var min = null;
var arr = [];
var len = array.length;
for(var i=0,j=len-1;i<j;) {
var start = array[i];
var end = array[j];
var _sum = start + end;
if(_sum < sum) {
i++;
}else if(_sum > sum) {
j--;
}else if(_sum == sum){
var t = start * end;
if(min == null || min > t) {
min = t;
arr = [start, end];
}
i++;
j--;
}
}
return arr;
}
var array = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20];
var sum = 21;
console.log(FindNumbersWithSum(array, sum)); // [1,20]
該解法的時間復雜度是n滴劲。
后語
身為前端er，也許業(yè)務上并不過多需要這種算法的使用顾复，但是適當?shù)乃惴}練習班挖，可以鍛煉自己的思維和代碼能力，故開此系列專題芯砸，希望可以堅持下去聪姿，做到每周一題。
