JavaScriptで2つの配列の合計を等しくする！要素交換アルゴリズムの解説

問題の概要

数値を格納した2つの配列 arr1 と arr2 を、それぞれ第1引数・第2引数として受け取るJavaScript関数を実装することを考えます。

ここで、arr1 の要素の合計と arr2 の要素の合計は互いに異なっています。この関数には次のような役割を持たせます。
まず arr1 から1つの要素を取り出して arr2 へ移動させ、同時に arr2 から1つの要素を取り出して arr1 へ移動させます。この操作によって、両方の配列の要素の合計が等しくなるようにします。最後に、交換した2つの要素を配列として返します。

例として、関数への入力が以下の場合を確認してみましょう。

入力

const arr1 = [1, 2, 5];
const arr2 = [2, 4];

出力

const output = [5, 4];

出力の解説

arr1 から 5 を取り除いて arr2 に追加し、arr2 から 4 を取り除いて arr1 に追加すると、両方の配列の合計はそれぞれ 7 となり、見事に一致します。そのため、答えは [5, 4] となります。

解法のアプローチ

全ての要素の組み合わせを総当たりで調べる方法もありますが、数学的な性質を利用すれば、より効率的に解けます。考え方は以下の通りです。

• まず、両方の配列の合計値 sumA と sumB をそれぞれ計算します。
• 交換後の目標となる合計値は、全体の合計の半分、つまり (sumA + sumB) / 2 です。
• arr1 から要素 x を抜き、arr2 から要素 y を受け取ったとき、条件式は sumA − x + y = (sumA + sumB) / 2 と表せます。これを変形すると y = x + difference（ただし difference = (sumA + sumB) / 2 − sumA）というシンプルな関係になります。
• そこで、arr2 の各要素をあらかじめハッシュマップ（オブジェクト）に登録しておけば、「x + difference が arr2 に存在するか」をO(1)で判定でき、全体の計算量はO(n)に抑えられます。

実装コード

const arr1 = [1, 2, 5];
const arr2 = [2, 4];
const balanceArrays = (arr1 = [], arr2 = []) => {
    const sumA = arr1.reduce((acc, v) => acc + v, 0)
    const sumB = arr2.reduce((acc, v) => acc + v, 0)
    const difference = (sumA + sumB) / 2 - sumA
    const map = arr2.reduce((acc, v) => {
        acc[v] = true
        return acc
    }, {})
    for(let i = 0; i < arr1.length; i++) {
        if(map[arr1[i] + difference] === true) {
            return [arr1[i], arr1[i] + difference]
        }
    }
    return []
};
console.log(balanceArrays(arr1, arr2));

出力結果

[5, 4]

コードのポイント

• reduce() を使うことで、配列の合計値やハッシュマップの生成を簡潔に記述できます。
• 条件を満たす組み合わせが存在しない場合は、空の配列 [] を返す仕様になっています。
• ハッシュマップによる検索により、二重ループを使う総当たり方式（O(n × m)）と比べて大幅に高速化でき、大きな配列でも実用的なパフォーマンスを発揮します。

このように、差分の関係式を導き出しハッシュマップと組み合わせることで、一見複雑に思える配列のバランス調整問題も、線形時間でエレガントに解くことができます。