最简单的方法是将 for 循环嵌套在另一个循环中。
但我想以这种方式解决它“检查数组是否同时包含desiredSum-x和x”
let givenArray = [1, 2, 5, 4, 4];
let desiredSum = 7;
// nested for loop
// for (i = 0; i < givenArray.length; i++) {
// for (j = i + 1; j < givenArray.length; j++) {
// if (givenArray[i] + givenArray[j] == desiredSum) {
// flag = 1;
// console.log(givenArray[i] + " & " + givenArray[j]);
// }
// }
// }
// generate all possible sums from desiredSum and check if both of required numbers are available
for (i = 0; i < givenArray; i++) {
if (givenArray.includes(i) && givenArray.includes(desiredSum-i)) {
console.log((desiredSum-x) + ' & ' + (x))
}
}
该desiredSum - x
和x
方法是通过实际完成的cache
机制。在迭代数组时,检查当前元素与 的差异,desiredSum
如果存在于 中cache
,则将其添加到output
数组中。否则,您会将当前数字存储在cache
.
时间复杂度 - O(n)
空间复杂度 - O(n)
let givenArray = [1, 2, 5, 4, 4,3];
let desiredSum = 7;
function twoSum(desiredSum,givenArray){
let output = [];
let cache = new Set();
for (let i = 0; i < givenArray.length; i++) {
const firstNumber = givenArray[i];
const secondNumber = desiredSum - firstNumber;
if(cache.has(secondNumber)){
output.push([firstNumber,secondNumber]);
}
else{
cache.add(firstNumber);
}
}
return output;
}
const result = twoSum(desiredSum,givenArray);
console.log(result);
本文收集自互联网,转载请注明来源。
如有侵权,请联系 [email protected] 删除。
我来说两句