JavaScriptで配列を連続する整数の部分列に分割できるか判定する方法

問題

ソート済みの整数配列 arr を引数として受け取る JavaScript 関数を作成します。

この関数は、配列を1つ以上の部分列（サブシーケンス）に分割でき、それぞれの部分列が連続した整数で構成され、長さが3以上である場合にのみ true を返し、それ以外の場合は false を返す必要があります。

例として、関数への入力が以下であるとします。

入力

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

出力

const output = true;

出力の説明

この配列は、次の2つの連続する部分列に分割できます。

1, 2, 3
3, 4, 5

それぞれの部分列が連続した整数（差が1ずつ増加）で構成され、長さも3以上あるため、結果は true となります。

アプローチ：貪欲法（グリーディ法）による解法

この問題は、各要素を処理する順序が重要になります。基本的な戦略は次のとおりです。

• 既存の部分列への追加を優先する： すでに作成済みの部分列の末尾に続けられる数値があれば、優先的に追加します。これにより、短すぎる部分列が残ることを防げます。
• 新しい部分列の作成： 既存の部分列に追加できない場合は、現在の数値から始まる長さ3の新しい部分列（num, num+1, num+2）を作れるか確認します。
• どちらも不可能なら false： 上記のいずれもできない場合、その数値はどこにも属せないため、分割は不可能です。

このアルゴリズムでは、次の2つのマップを使用します。

• count: 各数値の残りの出現回数を記録します。
• needed: 既存の部分列が「次に必要としている」数値を記録します。

コード例

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

const arr = [1, 2, 3, 3, 4, 5];
const canSplit = (arr = []) => {
    // 各数値の出現回数をカウント
    const count = arr.reduce((acc, num) => {
        acc[num] = (acc[num] || 0) + 1;
        return acc;
    }, {});
    // 既存の部分列が次に必要とする数値を管理
    const needed = {};
    for (const num of arr) {
        // 処理済みの数値はスキップ
        if (count[num] <= 0) {
            continue;
        }
        count[num] -= 1;
        // 既存の部分列に追加できる場合
        if (needed[num] > 0) {
            needed[num] -= 1;
            needed[num + 1] = (needed[num + 1] || 0) + 1;
        } else if (count[num + 1] > 0 && count[num + 2]) {
            // 新しい長さ3の部分列を作成
            count[num + 1] -= 1;
            count[num + 2] -= 1;
            needed[num + 3] = (needed[num + 3] || 0) + 1;
        } else {
            // どちらも不可能な場合は分割不可
            return false;
        }
    }
    return true;
};
console.log(canSplit(arr));

出力

true

計算量

• 時間計算量: O(n log n) — 配列がソート済みであれば O(n)、未ソートの場合はソートに O(n log n) かかります。
• 空間計算量: O(n) — カウント用のマップに配列の要素数分のメモリを使用します。