Pythonで配列の要素が連続しているかどうかをO(n)時間・O(1)空間で判定する方法（負の数にも対応）

ソートされていない整数の配列 nums が与えられます。この配列の要素が「連続した値」（連続する整数列）になっているかどうかを判定します。ここでは、負の数が含まれる場合にも対応します。

たとえば、入力が nums = [-3, 5, 1, -2, -1, 0, 2, 4, 3] の場合、要素を昇順に並べると -3, -2, -1, 0, 1, 2, 3, 4, 5 となり、欠けなく連続しています。そのため、出力は True になります。

解法の考え方：等差数列の和の公式を利用

連続した整数の配列は、「最小値を初項、公差1とする等差数列」とみなすことができます。等差数列の和は次の公式で求められます。

和 ＝ 要素数 × (2 × 初項 ＋ (要素数 − 1) × 公差) ÷ 2

この性質を利用し、以下の手順で判定を行います。

1. 配列のサイズ size を取得します。
2. 配列内の最小値を求め、これを初項 init_term とします。
3. 上記の公式から、連続していた場合に期待される合計値 ap_sum を計算します。
4. 配列の実際の合計値 total を求めます。
5. ap_sum と total が一致すれば True、そうでなければ False を返します。

実装例

def solve(nums):
    size = len(nums)
    init_term = float('inf')
    for i in range(size):
        if nums[i] < init_term:
            init_term = nums[i]
    ap_sum = (size * (2 * init_term + (size - 1) * 1)) // 2
    total = sum(nums)
    return ap_sum == total

nums = [-3, 5, 1, -2, -1, 0, 2, 4, 3]
print(solve(nums))

入力

[-3, 5, 1, -2, -1, 0, 2, 4, 3]

出力

True

計算量

• 時間計算量：O(n) — 最小値の探索と合計値の計算で、それぞれ配列を一度ずつ走査します。
• 空間計算量：O(1) — 追加のデータ構造を使わず、変数のみで処理します。

注意点：重複や偽陽性への対策

この手法は非常に効率的ですが、合計値が一致しても実際には連続していないケース（例：[0, 0, 3] のような重複を含む配列）を誤って True と判定する可能性があります。厳密な判定が必要な場合は、セット（集合）を組み合わせた次のような方法が確実です。

def solve_strict(nums):
    num_set = set(nums)
    # 重複がある場合は連続とはみなさない
    if len(num_set) != len(nums):
        return False
    # 最大値と最小値の差が要素数-1と一致すれば連続
    return max(num_set) - min(num_set) == len(nums) - 1

こちらの方法でも時間計算量は O(n) ですが、集合の分だけ追加メモリ O(n) が必要になります。パフォーマンスと厳密さのバランスを考慮し、用途に応じて使い分けるとよいでしょう。