JavaScriptの2-sumアルゴリズムを解く

Question

JavaScriptの2-Sum問題に対する簡単な解を書こうとしています。問題は次のようになります。n個の整数とターゲット合計の配列が与えられた場合、2つの整数のどの組み合わせがターゲット値に加算されるかを決定します。

私は、ハッシュテーブルを使用して、いくつかの異なる言語に依存しない例を発見し、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ループを歩くことができます。私は間違ったことをしているのを見ていますが、私が見つけたlangaugeの無関係な例（例えばhereとhere）に従っていると確信しています。どんな助けもありがとう。ここで

Answer 1

、あなたの出力指数加数の、あなたはその値必要ながら：

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

をあなたはこれらの値を取得する理由です：

• 3、1。つまり、インデックス3のアイテム+インデックス1のアイテム= 7
• 5,2;

  // 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]]); 
   
      } 
   
  }

  ：これは2 = 7等

arr[i]への出力にiを変更してみてください、そしてarr[hashTable[arg - arr[i]]]にhashTable[arg - arr[i]]は、それが動作するはずのインデックスでインデックス5 +アイテムの項目を意味します

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]); 
 
})

Answer 2

これを試してみてください：

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));