Pythonで重複要素のない最長の連続部分リストの長さを求めるプログラム

問題の概要

数値のリスト nums が与えられたとき、すべての要素が一意（重複なし）であるような最長の連続する部分リストの長さを求めることを考えます。

例えば、入力が nums = [6, 2, 4, 6, 3, 4, 5, 2] の場合、出力は 5 になります。これは、重複のない要素からなる最長の部分リストが [6, 3, 4, 5, 2] だからです。

解き方：スライディングウィンドウ法

この問題は「スライディングウィンドウ（尺取り法）」と呼ばれる手法で効率的に解けます。基本的な考え方は以下の通りです。

• ウィンドウの左端を指す head を 0 で初期化し、各要素の最後に出現したインデックスを記録する辞書 dct を用意します。

• 最大長を記録する変数 max_dist を 0 で初期化します。

• リスト内の各インデックス i と要素 num について、次の処理を行います。

  • num がすでに辞書に存在し、かつその記録位置が現在のウィンドウ範囲内（dct[num] >= head）であれば、ウィンドウの左端 head を dct[num] + 1 に移動して重複を排除します。

  • 辞書の dct[num] を現在のインデックス i で更新します。

  • 現在のウィンドウの長さ i - head + 1 が max_dist より大きければ、max_dist を更新します。

• ループ終了後、max_dist を返します。

実装例

それでは、実際のコードを見てみましょう。

class Solution:
    def solve(self, nums):
        head = 0
        dct = {}
        max_dist = 0
        for i, num in enumerate(nums):
            if num in dct and dct[num] >= head:
                head = dct[num] + 1
            dct[num] = i
            if i - head + 1 > max_dist:
                max_dist = i - head + 1
    return max_dist

ob = Solution()
nums = [6, 2, 4, 6, 3, 4, 5, 2]
print(ob.solve(nums))

入力

[6, 2, 4, 6, 3, 4, 5, 2]

出力

5

コードの動作解説

このアルゴリズムでは、リストを一度だけ走査しながら、重複が発生した時点でウィンドウの左端を「前回その値が出現した位置の次」まで一気に移動させます。これにより、常にウィンドウ内の要素がすべて一意であることが保証されます。

例えば [6, 2, 4, 6, 3, 4, 5, 2] の場合、インデックス 3 の「6」で重複が検出されると、head はインデックス 1 に移動し、以降は [2, 4, 6, 3, ...] のようなウィンドウで探索が続きます。最終的に [6, 3, 4, 5, 2] の長さ 5 が最大値として返されます。

計算量

• 時間計算量： O(n) — リストを一度だけ走査します。

• 空間計算量： O(n) — 最悪の場合、すべての要素を辞書に格納します。

全ての部分リストを総当たりで調べる O(n²) の素朴なアプローチと比べ、この手法は大規模なデータに対しても高速に動作するのが大きな利点です。