Pythonで最長連続シーケンスの長さを求めるアルゴリズムと実装方法

問題概要

ソートされていない数値の配列が与えられたとき、その中から連続する要素で構成される最長シーケンスの長さを見つける問題を考えてみましょう。ここでいう「連続」とは、値が1ずつ増えていく数列（例：4, 5, 6, 7）のことを指します。

例えば、入力が nums = [70, 7, 50, 4, 6, 5] の場合、最も長い連続シーケンスは [4, 5, 6, 7] となるため、答えは 4 になります。

解法のアプローチ

この問題は、以下の手順で効率的に解くことができます。

1. まず、配列をセット（set）に変換して重複を除去します。これにより、要素の存在確認が O(1) で行えるようになります。
2. 各要素 num について、「num - 1 がセットに存在しない場合」、その要素は連続シーケンスの始点であると判断できます。
3. 始点から順に num + 1、num + 2… と値が存在するかを確認し、シーケンスの長さをカウントします。
4. カウントした長さの最大値を記録し、最終的にそれを返します。

この「始点からのみ探索を開始する」という工夫により、同じシーケンスを何度も走査することを避けられます。

実装例

class Solution:
    def solve(self, nums):
        nums = set(nums)
        max_cnt = 0
        for num in nums:
            if num - 1 not in nums:
                cnt = 0
                while num in nums:
                    num += 1
                    cnt += 1
                max_cnt = max(max_cnt, cnt)
        return max_cnt

ob = Solution()
nums = [70, 7, 50, 4, 6, 5]
print(ob.solve(nums))

入力

[70, 7, 50, 4, 6, 5]

出力

4

計算量について

一見すると二重ループがあるため O(n²) に見えますが、実際には各要素は高々1回しか走査されないため、時間計算量は O(n) です。これは、内側の while ループが開始されるのは「シーケンスの始点」だけだからです。

また、セットへの変換に O(n) の空間計算量が必要となります。ソートを使う方法（O(n log n)）よりも高速に動作するのがこのアルゴリズムの大きな利点です。