JavaScriptで最大値と最小値の差がちょうど1となる最長部分配列を求める方法

問題の概要

数値の配列 arr を唯一の引数として受け取るJavaScript関数を作成することを目標とします。

この関数は、部分配列内の最大値と最小値の差がちょうど1 となる連続した要素の集まり（部分配列）の中から、最も長いものの長さを見つけて返す必要があります。

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

const arr = [2, 4, 3, 3, 6, 3, 4, 8];

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

const output = 5;

出力の解説

条件を満たす最長の部分配列は [4, 3, 3, 3, 4] です。この部分配列では最大値が4、最小値が3となり、その差はちょうど1。要素数は5個なので、答えは5となります。

実装コード

以下が実際のコード例です。

const arr = [2, 4, 3, 3, 6, 3, 4, 8];
const longestSequence = (arr = []) => {
    const map = arr.reduce((acc, num) => {
        acc[num] = (acc[num] || 0) + 1
        return acc
    }, {})

    return Object.keys(map).reduce((max, key) => {
        const nextKey = parseInt(key, 10) + 1
        if (map[nextKey] >= 0) {
            return Math.max(
                max,
                map[key] + map[nextKey],
            )
        }
        return max
    }, 0);
};
console.log(longestSequence(arr));

コンソール出力

5

コードの仕組み

このアプローチは、各ステップで次のように動作します。

1. 出現回数のカウント: 最初の reduce() を使って、配列内の各数値が出現する回数をオブジェクト（ハッシュマップ）として記録します。上記の例では { '2': 1, '3': 4, '4': 2, '6': 1, '8': 1 } のようなマップが生成されます。
2. 隣接する数値との組み合わせを確認: 次に、マップ内の各キーに対して「その数値 + 1」のキーが存在するかをチェックします。存在する場合、両方の出現回数を合計した値が候補の長さになります。
3. 最大値の更新: Math.max() を使って、これまでに見つかった最大の長さと比較しながら結果を更新していきます。

重要なポイントとして、差が1となる部分配列は必ず2種類の隣接する数値だけで構成されるため、元の配列の並び順を気にせず、出現回数だけを考慮すればよいのがこの手法の利点です。計算量は O(n) と効率的で、大きな配列でも高速に処理できます。