题解 | #和为S的两个数字#
和为S的两个数字
https://www.nowcoder.com/practice/390da4f7a00f44bea7c2f3d19491311b?tpId=13&&tqId=11195&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
function FindNumbersWithSum(array, sum) { let i = 0; let j = array.length - 1; let resTemp = [] while(i<j){ if(array[i] + array[j] === sum){ resTemp.push([array[i],array[j]]) } if(array[i] + array[j] >= sum){ j = j-1 } if(array[i] + array[j] <= sum){ i = i+1 } } let multArr = [] if(resTemp.length == 0){ return [] } for(let a = 0;a<resTemp.length;a++){ multArr.push(resTemp[a][0]*resTemp[a][1]) } let num = multArr.indexOf(Math.min(...multArr)) if(multArr.length === 0) return [] else return resTemp[num] } module.exports = { FindNumbersWithSum : FindNumbersWithSum };来自菜鸡的解答,昨天面试代码题就是这个,但是当时用的暴力破解,面试官看起来不太满意,然后当时也没想到其他方法,正好半夜睡不着刷题看到了别人的解法,但是没找到js的版本,就自己试着写了写,感觉有很多地方都可以优化,特别是最后取得乘积最小的两个值的部分。
思路:定义i为0,j为输入数组长度减一,将数组第i个元素和第j个元素相加,等于目标值则将两个数以数组的形式插入resTemp,若大于目标值则j-1,小于目标值则i+1,直到i不再小于j,然后对resTemp进行操作,计算其中存储的数组中的两项之积,然后插入multArr,取得multArr中最小的值的序号,即为resTemp中乘积最小的数组的序号,并且返回