javascript - 找到总和等于给定值且复杂度为 o(n) 的对

Question

我有一个包含数字的数组。我想找到一对总和等于给定值且复杂度为 o(n) 的数字。

let data = [5,8,9,6];

var x = {};

function findSum(arr, sum){

     data.forEach(function(item){
       if(item > sum){
         return null
       }
         var diff = sum - item;
       x[item] = diff
     })

  console.log(x);
}

findSum(data, 7);

复杂度为 O(n²)。

let data = [2, 4, 11, 3, 5, 8, 9, 1, 6, 5]

function findSum(arr, sum) {
  let sortArray = arr.sort(function(a, b) {
    return a - b
  });


  let findIndex = arr.indexOf(arr.find(function(item) {
    return item >= sum
  }))

  let iterateValues = sortArray.slice(0, findIndex);

  var pairs = [];
  console.log(iterateValues)
  iterateValues.forEach(function(value, index) {
    let getDiff = sum - value;
    let findDiff = iterateValues.find(function(diff, index) {
      return diff === getDiff
    });
    if (findDiff) {
      let firstPair = value.toString()
      let secondPair = findDiff.toString();
      let merge = firstPair + ',' + secondPair;
      pairs.push(merge)
    }
  })

  console.log(pairs)
}

findSum(data, 7);

Answer 1

尝试以下操作，需要 O(n) 时间才能找到总和等于给定值的对:

let data = [5,8,9,6];
var sum = 17;
var map = {};
var found = false;
for(var i = 0; i < data.length; i++){
  map[data[i]] = i;
}

for(var i = 0; i < data.length; i++){
  if(map[sum - data[i]] && map[sum - data[i]] != i){
    found = true;
    console.log(data[map[sum - data[i]]] + " "+data[i]);
    break;
  }
}
if(!found)
  console.log("No pair found");