JavaScriptで0と1が同数含まれる最長の連続部分配列を求める方法

問題

二進配列（0と1のみで構成される配列）arr を引数として受け取り、0と1の個数が等しくなる連続する部分配列のうち、最長のものの長さを返すJavaScript関数を作成します。

例えば、次の入力が与えられた場合を見てみましょう。

const arr = [1, 0, 0, 1, 0, 1, 0, 0];

この場合の出力は次のようになります。

const output = 6;

出力の説明

配列の最初の6要素は「1, 0, 0, 1, 0, 1」です。ここには1が3つ、0が3つ含まれており、条件を満たす最長の連続部分配列となっているため、答えは6になります。

サンプルコード

この問題を解くコードは以下の通りです。

const arr = [1, 0, 0, 1, 0, 1, 0, 0];
const findMaxLength = (arr = []) => {
    const { length } = arr;
    if (length < 2){
        return 0
    };
    const map = new Map();
    map.set(0, -1);
    let sum = 0;
    let max = 0;
    for (var i = 0; i < length; i++) { 
        sum += arr[i] === 0 ? -1 : 1;
        if (map.has(sum)) {
            max = Math.max(max, i - map.get(sum));
        } else {
            map.set(sum, i);
        };
    };
    return max;
};
console.log(findMaxLength(arr));

コードの解説

このアルゴリズムのポイントは、0を-1、1を+1として扱うことです。こうすることで、ある区間内の合計値が0になれば、その区間には必ず同数の0と1が含まれていることが分かります。

具体的には、配列を左から順に走査しながら累積和 sum を計算し、Map を使って各累積和が最初に出現したインデックスを記録していきます。同じ累積和が再び現れた場合、その2つのインデックスの間にある部分配列は0と1の個数が等しいため、i - map.get(sum) で長さを求め、最大値を更新します。

また、初期状態で map.set(0, -1) としているのは、配列の先頭から始まる部分配列にも対応するためです。これにより、累積和が0になった地点までの区間も正しく評価できます。

この手法により、全ての部分配列を総当たりするO(n²)のアプローチを避け、時間計算量O(n)・空間計算量O(n)という効率的な解法を実現できます。

実行結果

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

6