每周一题 - 求和为S的两个数字

题目

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

求解思路

思路一

开始拿到题目，最先想到的是两个for循环，将之遍历，可得出答案。

但是，如果这个数组很大，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说明相加的数小了，所以头部向中间进一步。
3+10>12说明相加的数大了，所以尾部向中间进一步。
以此类推，直到头尾的指向都停留在中间，该遍历结束。

上代码

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，也许业务上并不过多需要这种算法的使用，但是适当的算法题练习，可以锻炼自己的思维和代码能力，故开此系列专题，希望可以坚持下去，做到每周一题。