Pythonで配列に連続した整数（重複可）が含まれているか判定する方法

はじめに

Pythonでは、数値の配列（リスト）に連続した整数が含まれているかどうかを判定したい場面があります。ここでの「連続」とは、要素が重複していてもよいものの、値そのものは途切れることなく並んでいる状態を指します。

例えば、次のようなリストを考えてみましょう。

nums = [6, 8, 8, 3, 3, 3, 5, 4, 4, 7]

このリストには重複する要素が含まれていますが、ユニークな値を取り出すと 3, 4, 5, 6, 7, 8 となり、途切れのない連続した整数になっています。この場合、判定結果は True となります。

解決のアプローチ

この問題は、以下の手順でシンプルに解決できます。

1. リスト nums を昇順にソートします。
2. インデックス 1 から最後まで走査し、隣接する要素同士の差を確認します。
3. もし nums[i] - nums[i-1] が 1 より大きい場合、数列に「抜け」があるため False を返します。
4. すべての隣接要素の差が 1 以下であれば、連続した整数とみなせるため True を返します。

ソート後は同じ値が隣り合うため、差が 0 の場合は重複として無視され、差が 1 の場合は連続していると判断されます。差が 2 以上になると、そこで数列が途切れていることになります。

実装例

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

def solve(nums):
    nums.sort()
    for i in range(1, len(nums)):
        if nums[i] - nums[i-1] > 1:
            return False
    return True

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

入力

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

出力

True

計算量について

このアルゴリズムの計算量は、ソート処理が支配的となるため O(n log n) です。走査部分は線形時間 O(n) で完了します。

なお、set() を使って重複を除去してから最小値・最大値の差と要素数を比較する方法もありますが、この方法でもソートベースの手法と同様に O(n log n) の計算量となります。状況に応じて読みやすい方を選択するとよいでしょう。

まとめ

配列をソートして隣接要素の差を確認するだけで、重複を含むリストが連続した整数で構成されているかどうかを簡単に判定できます。コードも短く直感的なので、面接や実務の両方で役立つテクニックです。