【JavaScript】配列を合計が等しい3つの部分に分割できるか判定する方法

問題概要

整数の配列を唯一の引数として受け取るJavaScript関数を作成します。この関数は、配列を合計が等しい3つの空でない部分に分割できる場合にのみ true を返し、それ以外の場合は false を返す必要があります。

例えば、関数への入力が次の場合を考えてみましょう。

const arr = [3, 3, 6, 5, -2, 2, 5, 1, -9, 4];

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

const output = true;

出力の解説

この入力が true になる理由は、配列を以下のように3つに分割でき、それぞれの合計が等しくなるからです。

3 + 3 = 6 = 5 - 2 + 2 + 5 + 1 - 9 + 4

つまり「[3, 3]」「[6]」「[5, -2, 2, 5, 1, -9, 4]」という3つの部分に分けると、いずれも合計が6になり条件を満たします。

解法のアプローチ

この問題は、次の手順で効率よく解くことができます。

1. 合計の計算: reduce() を使って配列全体の合計を求めます。
2. 割り切れるかの確認: 合計が3で割り切れない場合、等しい合計の3分割は不可能なので即座に false を返します。
3. 目標値との照合: 目標値(合計 ÷ 3)を設定し、配列を先頭から走査しながら累積和を追跡します。累積和が目標値に達したらカウンターを増やし、累積和をリセットします。
4. 最終判定: 走査終了時にカウンターがちょうど3で、残りの累積和が0であれば true を返します。

この方法なら、配列を一度走査するだけで済むため、時間計算量は O(n) と非常に効率的です。

実装コード例

const arr = [3, 3, 6, 5, -2, 2, 5, 1, -9, 4];
const thirdSum = (arr = []) => {
    const sum = arr.reduce((acc, val) => acc + val, 0);
    if (!Number.isInteger(sum / 3)) {
        return false;
    };
    let count = 0;
    let curr = 0;
    const target = sum / 3;
    for (const num of arr) {
        curr += num;
        if (curr === target) {
            curr = 0;
            count += 1;
        };
    };
    return count === 3 && curr === 0;
};
console.log(thirdSum(arr));

実行結果

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

true

まとめ

本記事では、配列を合計が等しい3つの部分に分割できるかどうかを判定するJavaScript関数を実装しました。ポイントは以下の3点です。

• まず合計を求め、3で割り切れない場合は早期リターンする
• 累積和を目標値と比較しながら配列を一回だけ走査する
• カウンターが3かつ余剰の累積が0であることを最終条件とする

負の数が含まれる配列にも対応できる堅牢な実装となっているため、コーディングテストやアルゴリズムの練習にも最適な例題です。