Pythonで一意な要素からなる最長の連続サブリストの長さを求める方法

重複のない（すべての要素が一意な）数値リスト nums が与えられたとき、その中から「連続する整数で構成される最長の部分リスト」の長さを求める問題を考えます。

例えば、nums = [3, 6, 7, 5, 4, 9] の場合、答えは 5 になります。これは、部分リスト [3, 6, 7, 5, 4] が 3 から 7 までの連続する整数をすべて含んでいるためです。

解法のアプローチ

この問題は、すべての部分リストを走査する O(n²) のアプローチで効率よく解けます。ポイントは以下の通りです。

• 各開始位置 i について、終了位置 j を右へ伸ばしながら、範囲内の最小値 lhs と最大値 rhs を順次更新します。
• 要素がすべて一意であるため、「最大値 − 最小値 ＝ 要素数 − 1」が成り立つとき、その部分リストは連続する整数で構成されていると判定できます。
• 条件を満たすたびに、これまでの最長の長さを記録しておき、最後にその値を返します。

具体的な手順

• ret := 0（答えを格納する変数）で初期化する
• i を 0 から リストの末尾まで繰り返す
  • lhs := nums[i]、rhs := nums[i] とする
  • j を i から リストの末尾まで繰り返す
    • lhs := min(lhs, nums[j])
    • rhs := max(rhs, nums[j])
    • rhs - lhs == j - i ならば、ret := max(ret, j - i + 1)
• ret を返す

実装例

以下のPythonコードで実際の動作を確認できます。

def solve(nums):
    ret = 0
    for i in range(len(nums)):
        lhs = nums[i]
        rhs = nums[i]
        for j in range(i, len(nums)):
            lhs = min(lhs, nums[j])
            rhs = max(rhs, nums[j])
            if rhs - lhs == j - i:
                ret = max(ret, j - i + 1)
    return ret

nums = [3, 6, 7, 5, 4, 9]
print(solve(nums))

入力

[3, 6, 7, 5, 4, 9]

出力

5

計算量について

このアルゴリズムの時間計算量は O(n²)、空間計算量は O(1) です。二重ループで全ての部分リストを確認しますが、最小値・最大値のみを保持するため追加のメモリはほとんど不要です。入力リストのサイズが数千程度であれば十分実用的な速度で動作します。