JavaScriptで高々2種類の数値を含む最大スライス（部分配列）を求める方法

問題の概要

配列を引数として受け取り、2種類以下の異なる数値のみを含む最長の連続した部分配列（スライス）を返す関数を作成することを考えてみましょう。

この問題を注意深く分析すると、安定した（条件を満たす）部分配列を判定しながら、元の配列を順番に走査していく処理が必要であることがわかります。

このようなケースでは、スライディングウィンドウ（Sliding Window）アルゴリズムが非常に有効です。ウィンドウの右端を拡張しつつ、異なる数値の種類数が2を超えた時点で左端を縮めることで、効率的に最長部分配列を探索できます。

実装コード

スライディングウィンドウアルゴリズムを使った解法のコードは以下のとおりです。

const arr = [1, 1, 1, 2, 2, 2, 1, 1, 2, 2, 6, 2, 1, 8, 1, 1 ,1 ,1, 8, 1, 1, 8, 8];
const map = {
    length: 0
};
let required = [];
for(start = 0, end = 0; end <= arr.length; ){
    if(map.length > 2){
        if(map[arr[start]] === 1){
            delete map[arr[start]];
            map.length --;
        }else{
            map[arr[start]]--;
        };
        start++;
    }else{
        if(end - start > required.length){
            required = arr.slice(start, end);
        };
        if(map[arr[end]]){
            map[arr[end]]++;
        }else{
            map[arr[end]] = 1;
            map.length++;
        }
        end++;
    }
}
console.log(required);

コードの解説

この実装では、mapオブジェクトを使って、任意の時点における各数値の出現回数と異なる数値の種類数（map.length）を管理しています。

処理の流れは以下のとおりです。

• ウィンドウ内の異なる数値の種類数が2以下の場合：現在のウィンドウ幅（end - start）がこれまでの最長記録より長ければ結果を更新し、右端を1つ進めてウィンドウを拡張します。
• 種類数が3以上になった場合：左端の要素のカウントを減らし、カウントが0になった要素をマップから削除して種類数を減算します。その後、左端を1つ進めます。

こうして、異なる数値が2種類を超えるたびにウィンドウを右方向へスライドさせながら、次の安定した部分配列を探索し続けます。各要素は最大で2回しか訪問されないため、計算量はO(n)となり非常に効率的です。

出力結果

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

[
    1, 8, 1, 1, 1,
    1, 8, 1, 1, 8,
    8
]

この結果は、「1」と「8」という2種類の数値だけで構成される、長さ11の最長部分配列を示しています。