在javascript中求解2和算法

solving the 2-sum algorithm in javascript

本文关键字：算法 javascript      更新时间：2023-09-26

我试图在Javascript中编写一个简单的2-Sum问题解决方案。问题是:给定一个n个整数的数组和一个目标和，确定两个整数的什么组合和为目标值。

我发现了一些使用哈希表的不同语言无关的例子，并试图在javascript中提出一个解决方案:

// Integer set:
arr = [1,4,2,3,0,5];
// Target sum:
arg = 7;
// Generate hash table
hashTable = {};
arr.forEach(function(value, index){ 
  hashTable[value] = index;
});
// hashTable = {
//   0: 4,
//   1: 0,
//   2: 2,
//   3: 3,
//   4: 1,
//   5: 5,
// }

for (var i = 0; i < arr.length; i++) {
  if (hashTable[arg - arr[i]]) {
      console.log([hashTable[arg - arr[i]], i])
  }
}

解应该是4,3和5,2但我得到的是3,1,5,2,1,3和2,5。我可以用笔和纸来遍历for循环，看看我做错了什么，但我很确定我是在遵循我发现的语言无关的例子(例如这里和这里)。任何帮助都会很感激。

这里，您输出求和的索引，而您需要它的值:

 console.log([hashTable[arg - arr[i]], i])

这就是为什么你得到这些值:

  • 3, 1;这意味着索引3的项目+索引1的项目= 7
  • 5, 2;这意味着索引5的项目+索引2的项目= 7等。

尝试将输出中的i改为arr[i]，将hashTable[arg - arr[i]]改为arr[hashTable[arg - arr[i]]]，应该可以工作:

// Integer set:
var arr = [1,4,2,3,0,5];
// Target sum:
var arg = 7;
// Generate hash table
var hashTable = {};
arr.forEach(function(value, index){ 
  hashTable[value] = index;
});
for (var i = 0; i < arr.length; i++) {
  if (hashTable[arg - arr[i]]) {
      console.log([arr[hashTable[arg - arr[i]]], arr[i]]);
  }
}

注意，你也得到对称的结果，因为4 + 3 = 7和3 + 4 = 7。
可以通过在插入

时检查来优化解决方案。

var arr = [1, 4, 2, 3, 0, 5];
var arg = 7;
var hashtable = {};
arr.forEach(function(x) { 
  hashtable[x] = true;
  if (hashtable[arg - x]) 
    console.log([arg - x, x]); 
})

function solution(arr, n){
var map = {};
for (var i = 0; i < arr.length; i++) {
    if (map[arr[i]] !== undefined) {
        console.log(arr[i], n - arr[i]);
    }
    map[n - arr[i]] = i;
  }
 }

试一下:

function sumPairs(inputArray, expectedSum){
  var a = inputArray.slice(), b = inputArray.slice(), l = a.length, p = [];
  for(var i=0,av; i<l; i++){
    av = a[i];
    for(var n=1,bv; n<l; n++){
      bv = b[n];
      if(av + bv === expectedSum){
        p.push([av, bv]);
      }
    }
  }
  return p;
}
console.log(sumPairs([1,4,2,3,0,5], 7));

下面的函数可以正常工作。

   const twoSum = (numArr, target) => { 
        let numObject = {};
        numArr.forEach((value, index) => numObject[value] = index);
        for (let i = 0; i < numArr.length; i++) {
            let diff = target - numArr[i];
            if (numObject.hasOwnProperty(diff) && numObject[diff] !== i) {
                return [i, numObject[diff]];
            }
        }
    }


const arr = [1, 2, 3, 4,5,6];
let target = 9;
let indexs = [];
function sumNew(arr, target) {
    for (let i = 0; i < arr.length; i++) {
        for (let j = i+1; j < arr.length; j++) {
            if ( arr[i] + arr[j]==target) {
               indexs.push(i,j);
               return indexs;
            }
        }
    }
}
let result = sumNew(arr,target);
console.log(result);

相关文章：