Pythonで配列の要素が連続しているかどうかを判定する方法

数値の配列 nums が与えられたとき、その要素が連続した値（連番）になっているかどうかを判定する問題を考えてみましょう。

たとえば、入力が nums = [6, 8, 3, 5, 4, 7] の場合、要素を並べ替えると 3, 4, 5, 6, 7, 8 となり途切れがないため、出力は True になります。

解法のアプローチ

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

1. 配列のサイズが1未満の場合は False を返します。
2. 配列の最小値 min_val と最大値 max_val を求めます。
3. (max_val - min_val + 1) が配列のサイズと一致しない場合、その範囲内に必ず重複や欠落が生じるため、連続にはなり得ません。この時点で False を返します。
4. 一致する場合は、要素の符号を反転させるテクニックで重複チェックを行います。
   • 各要素について、nums[i] が負なら j = -nums[i] - min_val、そうでなければ j = nums[i] - min_val を計算します。
   • nums[j] が正であれば符号を反転して「訪問済み」の印をつけます。
   • すでに負（訪問済み）であれば重複があるため False を返します。
5. すべての要素を処理できれば True を返します。

この手法では、セットや辞書などの追加データ構造を使わず、配列自身をフラグ代わりに利用できるため、追加メモリ O(1)・時間計算量 O(n) で実現できるのが大きな特徴です。

実装例

def solve(nums):
    if len(nums) < 1:
        return False
    min_val = min(nums)
    max_val = max(nums)
    if max_val - min_val + 1 == len(nums):
        for i in range(len(nums)):
            if nums[i] < 0:
                j = -nums[i] - min_val
            else:
                j = nums[i] - min_val
            if nums[j] > 0:
                nums[j] = -nums[j]
            else:
                return False
        return True
    return False

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

入力

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

出力

True

コードの解説

まず、最小値と最大値の差から、理論上必要な値の範囲の幅を計算します。この幅が配列の長さと一致しなければ、整数の連番として成立しないため即座に False を返せます。

幅が一致する場合は、各値 v をインデックス j = v - min_val にマッピングし、対応する要素の符号を負にすることで「この値は既に確認済み」という印をつけていきます。同じ値が2回現れると同じ位置が2回マーキングされるため、2回目の時点で False を返すことで重複を検出できます。

なお、この方法は元の配列の内容を書き換えてしまう点に注意してください。元の配列を保持したい場合は、処理前にコピーを作成しておきましょう。