JavaScriptの最適化ペア検索アルゴリズム

Question

私は整数と配列の配列を引数としてとるjavascript関数を作成しています。タスクは、その合計がターゲットと等しい整数の最初のペアを見つけることです。私はこれをいくつかの方法で試しましたが、大きな入力配列ではタイムアウトエラーが続きます。誰かが私にこのコードをより良く最適化する方法についていくつかの指摘をしてくれますか？ありがとう！訪問した値要素の

変数aarray[i]

非常に短い変数名の

var sum_pairs = function(ints, s){ 
    var r = []; 
    var a = true; 
    var l = ints.length; 
    for(var j = 0; j < l; j++){ 
    if(a){ 
     for(var i = 0; i < j; i++){ 
     if(ints[j] + ints[i] == s){ 
      r[0] = ints[i]; 
      r[1] = ints[j]; 
      a = false; 
      break; 
     } 
     } 
    } 
    else{ 
     console.log('breaking'); 
     break; 
    } 
    } 
return r[0] == null ? null : r; 
} 

Answer 1

あなたは

• シングルループのように、いくつかの高速化メカニズムを使用することができますが、
• ハッシュテーブル（冗談）

Long listが必要です。153 msです。私たちは、配列を反復しながら、我々はSetにその数の予想パートナーtarget - numberを追加遭遇番号ごと

var sum_pairs = function (array, s) { 
 
    var a, i, 
 
     hash = Object.create(null); 
 

 
    for (i = 0; i < array.length; i++) { 
 
     a = array[i]; 
 
     if (hash[s - a]) { 
 
      return [s - a, a]; 
 
     } 
 
     if (!hash[a]) { 
 
      hash[a] = true; 
 
     } 
 
    } 
 
}; 
 

 
console.log(sum_pairs([11, 3, 7, 5], 10));  // [3, 7] 
 
console.log(sum_pairs([4, 3, 2, 3, 4], 6));  // [4, 2] 
 
console.log(sum_pairs([0, 0, -2, 3], 2));   // undefined 
 
console.log(sum_pairs([10, 5, 2, 3, 7, 5], 10)); // [3, 7] 
 
console.log(sum_pairs([1, 2, 3, 4, 1, 0], 2)); // [1, 1] 
 
console.log(sum_pairs([1, -2, 3, 0, -6, 1], -6)); // [0, -6] 
 
console.log(sum_pairs([0, 2, 0], 0));    // [0, 0] 
 
console.log(sum_pairs([5, 9, 13, -3], 10));  // [13, -3]

.as-console-wrapper { max-height: 100% !important; top: 0; }

Answer 2

。私たちがセットにすでにある数に遭遇するとすぐに、私たちは、そのパートナーが既に発生したソリューションとして、このペアを返してきたことを知っている：

// Return the first two values of 'numbers' summing up to 'target': 
 
function sum_pairs(numbers, target) { 
 
    let paired = new Set(); 
 
    for (let number of numbers) { 
 
    if (paired.has(number)) return [target - number, number]; 
 
    paired.add(target - number); 
 
    } 
 
} 
 

 
// Examples: 
 
console.log(...sum_pairs([9, 3, 7, 5, 1], 10)); // [3, 7] 
 
console.log(...sum_pairs([4, 3, 2, 3, 4], 6)); // [4, 2] 
 
console.log(...sum_pairs([9, 3, 6, 4, 1], 10)); // [6, 4]

この実装は、線形のランタイムを持っていますしたがって、長い入力配列の方が高速ですが、追加のメモリコストがかかります。

未処理の速度の場合はfor-ofループを従来のforループに置き換え、変数バインディングをvar宣言で置き換えます。