从给定数组中查找一对元素，其和等于JavaScript中的特定目标数

Question

在Javascript中，还有其他有效的方法来实现此任务吗？

我尝试的身份是：

const a1 = [1,3,4,2,5,7,8,6];
var newArray =[];

function fun(a,n){      

for(let i = 0; i<a.length; i++){
 for(let j=i+1; j<a.length; j++){        
   if((a[i]+a[j])==n){        
     newArray.push([a[i],a[j]]);       
    }
  }
 }
}     

fun(a1, 10)
console.log(newArray);

这里输出：

[(3,7),(4,6),(2,8)]

Answer 1

这是一个通常称为“二和问题”的一般编程问题，它本身是子集和问题的子集。但无论如何都可以有效地解决，我用这篇文章作为灵感。

js lang-js prettyprint-override">const a1 = [1, 3, 4, 2, 5, 7, 8, 6];

// our two sum function which will return
// all pairs in the array that sum up to S
function twoSum(arr, S) {

  const sums = [];
  const hashMap = new Map();

  // check each element in array
  for (let i = 0; i < arr.length; i++) {

    // calculate S - current element
    let sumMinusElement = S - arr[i];

    // check if this number exists in hash map
    // if so then we found a pair of numbers that sum to S
    if (hashMap.has(sumMinusElement.toString())) {
      sums.push([arr[i], sumMinusElement]);
    }

    // add the current number to the hash map
    hashMap.set(arr[i].toString(), arr[i])
  }

  // return all pairs of integers that sum to S
  return sums;
}

console.log(twoSum(a1, 10))

Answer 2

我认为从暴力的角度来看，你的方法是有道理的。

在优化方面，我想到了几件事。

>

可以按升序对列表进行排序，当总和超过目标值时，可以跳过内部循环的其余部分。

Answer 3

这个问题被标记为javascript，但这个答案基本上与语言无关。

如果数组已排序（或者您可以对其进行排序），您可以遍历数组并为其中的每个元素x在数组中二进制搜索（目标-x）。这为您提供了O（nlogn）运行时间。

如果可以使用额外内存，可以使用数组的元素填充字典，然后针对数组中的每个元素x，在字典中查找（target-x）。如果您的字典是在哈希表上实现的，那么这将为您提供O（n）运行时间。