JavaScriptで合計が特定の値になる2つの数を配列から見つける最良の方法

はじめに

まず、次のような配列を例に考えてみましょう。

var numbers = [10, 3, 40, 50, 20, 30, 100]

この配列の要素の中から、合計が80になる2つの数を探します。

解決方法

最も効率的なのは、オブジェクト（ハッシュマップ）を活用するアプローチです。各要素に対して「目標値から現在の数を引いた補完値」を記録していき、後から同じ数が出現した時点でペアが確定します。これにより、二重ループによる総当たり方式（計算量 O(n²)）ではなく、線形時間 O(n) で解くことができます。

具体的には、for...of ループで配列を走査しながら、if 条件でペアの存在を判定します。

サンプルコード

function specificPairsOfSumOfTwoNumbers(numbers, totalValue) {
  var storeTwoNumbersObject = {}
  for (var currentNumber of numbers) {
    if (storeTwoNumbersObject[currentNumber]) {
      return {
        firstNumber: totalValue - currentNumber,
        secondNumber: currentNumber
      }
    }
    storeTwoNumbersObject[totalValue - currentNumber] = true;
  }
  return false;
}
var numbers = [10, 3, 40, 50, 20, 30, 100]
console.log("The Two numbers which has the sum 80=");
console.log(specificPairsOfSumOfTwoNumbers(numbers, 80))

プログラムの実行方法

上記のプログラムを実行するには、以下のコマンドを使用します。

node fileName.js

ここでは、ファイル名を demo207.js としています。

実行結果

プログラムを実行すると、以下の出力が得られます。

PS C:\Users\Amit\javascript-code> node demo207.js
The Two numbers which has the sum 80=
{ firstNumber: 50, secondNumber: 30 }

仕組みの解説

このアルゴリズムのポイントは以下の通りです。

• 配列の各要素について、「目標値 − 現在の数」＝「ペアとなるべき数」を計算し、オブジェクトに記録します。
• それ以降の要素が、すでに記録済みの数と一致した時点で、目的のペアが見つかったことになります。
• この例では、50 を処理した時点で 80 − 50 = 30 が記録され、続く 30 に到達した瞬間にペア {50, 30} が返されます。

ループを完了してもペアが見つからなかった場合は false を返します。計算量・空間計算量ともに O(n) であり、ネストしたループで全組み合わせを調べる O(n²) の方法よりも大幅に高速です。大きな配列を扱う場合に特に有効な手法といえます。