JavaScriptで合計が指定値と一致するトリプレットをすべて見つける方法

この記事では、数値の配列を第1引数として、目標値となる数値を第2引数として受け取り、合計が目標値と一致するすべてのトリプレット（3つの数の組み合わせ）を配列にまとめて返すJavaScript関数の作り方を解説します。トリプレットを構成する3つの要素は、配列内で隣接している必要はなく、離れた位置にある要素同士の組み合わせでも問題ありません。

入力例と期待される出力

たとえば、次のような配列と数値が与えられたとします。

const arr = [4, 2, 0, 1, 2, 6, 8, 3, 2, 5];
const num = 8;

この場合、出力される配列は次のようになります。

const output = [
  [ 2, 2, 4 ],
  [ 1, 3, 4 ],
  [ 0, 2, 6 ],
  [ 1, 2, 5 ]
];

サンプルコード

以下が実際のコードです。

const arr = [4, 2, 0, 1, 2, 6, 8, 3, 2, 5];
const num = 8;

const tripletSum = (arr, num) => {
  // 配列の要素数がちょうど3の場合の特別処理
  if (arr.length === 3) {
    if (arr[0] + arr[1] + arr[2] === num) {
      return [[arr[0], arr[1], arr[2]]];
    }
  }

  const results = [];
  const hashMap = {};

  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      for (let k = j + 1; k < arr.length; k++) {
        if (arr[i] + arr[j] + arr[k] === num) {
          const key = arr[i] * arr[j] * arr[k];
          // 同じ積を持つ組み合わせは重複として除外
          if (!hashMap[key]) {
            results.push([arr[i], arr[j], arr[k]]);
            results[results.length - 1].sort();
            hashMap[key] = true;
          }
        }
      }
    }
  }
  return results;
};

console.log(tripletSum(arr, num));

実行結果

コンソールには次のように表示されます。

[ [ 2, 2, 4 ], [ 1, 3, 4 ], [ 0, 2, 6 ], [ 1, 2, 5 ] ]

アルゴリズムのポイント

全探索による組み合わせの列挙

変数 i・j・k を使った3重ループにより、配列から選択可能なすべての3要素の組み合わせを漏れなく調べます。各組み合わせの合計が目標値 num と一致した場合のみ、結果として採用します。

ハッシュマップによる重複の排除

同じ3つの数値でも、選ぶ順序が異なるだけで何度もマッチしてしまいます。そこで、3つの値の積をハッシュマップのキーとして記録し、すでに登録済みの組み合わせは二度と追加しないようにしています。これにより、出力には意味の異なるトリプレットだけが残ります。

計算量に関する補足

3重ループを使用しているため、時間計算量は O(n³) となります。小規模な配列であれば十分実用的ですが、要素数が多いケースでは、あらかじめ配列をソートしておき、2ポインタ法を組み合わせることで O(n²) まで高速化できます。また、より厳密に重複判定を行いたい場合は、積ではなくソート後の3値を文字列連結したものをキーに使う方法も有効です。