JavaScriptの配列から合計が指定値になる3つの要素を見つける方法

本記事では、第1引数として数値の配列を、第2引数として単一の数値を受け取るJavaScript関数の実装方法を解説します。この関数は、配列の中から合計が第2引数で指定した数値と等しくなるような3つの要素を取り出します(該当する組み合わせが存在する場合)。

最終的に、関数は条件を満たすすべてのトリプレット(3つの組)を「配列の配列」として返し、該当する組み合わせがひとつも存在しない場合には空の配列を返します。

入力例と出力例

たとえば、入力の配列と目標となる合計値が以下であるとします。

const arr = [2, 5, 7, 8, 9, 11, 1, 6];
const sum = 22;

この場合、期待される出力は次のとおりです。

const output = [ [ 2, 9, 11 ], [ 5, 6, 11 ], [ 5, 8, 9 ], [ 6, 7, 9 ] ];

アルゴリズムの考え方

この問題を効率よく解くには、「ソート + 双方向ポインタ(two pointers)」というテクニックが有効です。大まかな流れは以下の通りです。

• まず配列を昇順にソートします。
• 各要素を基準値として固定し、残りの範囲に対して左端と右端にポインタを置きます。
• 3つの要素の合計が目標値より小さければ左ポインタを右へ、大きければ右ポインタを左へ移動させて調整します。
• 合計が目標値と一致したら結果に追加し、同じ値の要素をスキップすることで重複した解を防ぎます。

この手法を使えば、すべての組み合わせを総当たりするO(n³)のアプローチではなく、O(n²)の時間計算量で問題を解くことができます。

サンプルコード

実際のコードは以下のようになります。

const arr = [2, 5, 7, 8, 9, 11, 1, 6];
const sum = 22;

const threeSum = (arr = [], sum) => {
  // 配列を昇順にソート
  arr.sort((a, b) => a - b);
  const res = [];

  for (let i = 0; i < arr.length - 2; i++) {
    // 基準値が直前の要素と重複する場合はスキップ
    if (arr[i] !== arr[i - 1]) {
      let left = i + 1;
      let right = arr.length - 1;

      while (left < right) {
        const curr = arr[i] + arr[left] + arr[right];

        if (curr === sum) {
          res.push([arr[i], arr[left], arr[right]]);
          // 重複した解が結果に含まれないよう、同じ値をスキップ
          while (arr[left] === arr[left + 1]) left++;
          while (arr[right] === arr[right - 1]) right--;
          left++;
          right--;
        } else if (curr < sum) {
          left++;
        } else if (curr > sum) {
          right--;
        }
      }
    }
  }
  return res;
};

console.log(threeSum(arr, sum));

実行結果

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

[ [ 2, 9, 11 ], [ 5, 6, 11 ], [ 5, 8, 9 ], [ 6, 7, 9 ] ]

まとめ

配列をあらかじめソートしておき、双方向ポインタで絞り込みを行うことで、合計が指定値になる3つの要素の組み合わせを効率的に列挙できます。重複チェックを適切に行うことで、余分な組み合わせが結果に混ざることもありません。同様のアプローチは「4つの要素の合計」問題などにも応用できるため、ぜひ覚えておきましょう。