Pythonでリスト内の重複要素を検出するプログラム ― O(n)時間・定数空間の解法

サイズが n + 1 の整数リスト nums があり、その要素はすべて範囲 1, 2, ..., n の中から選ばれているとします。

このとき、鳩の巣原理（Pigeonhole Principle）より、リスト内には必ず少なくとも1つの重複した値が存在します。この重複している要素を見つけるのが本記事の目的です。

さらに、ここでは計算量 O(n)・追加メモリ O(1)（定数空間）という制約のもとで解くことを目標とします。

問題の例

たとえば、入力が次のような場合を考えてみましょう。

nums = [2, 1, 4, 3, 5, 4]

この場合、重複している値は 4 なので、出力は 4 となります。

解法の考え方

この問題は「合計値の差」を使うことで、ソートやハッシュセットなしに効率的に解けます。手順は以下の通りです。

• q : リスト nums 内の全要素の合計値

• n : リスト nums のサイズ

• v : (n - 1) * n / 2 の小数点以下切り捨て値（＝1から n-1 までの総和）

• q - v を返す（これが重複要素となる）

なぜこれで重複が見つかるのか？

リストのサイズは n + 1 ですが、実際に使われる値は 1 から n-1 までの範囲です。もし重複がなければ、リストの合計は 1 + 2 + ... + (n-1) = (n-1) * n / 2 になるはずです。

しかし実際には1つ余分な要素（重複分）が含まれているため、実際の合計から理論上の合計を引いた差が、そのまま重複要素の値になります。

Pythonでの実装例

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

def solve(nums):
   q = sum(nums)
   n = len(nums)
   v = (n - 1) * (n) // 2
   return q - v

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

入力

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

出力

4

まとめ

この手法は、リストを走査して合計を取るだけなので時間計算量 O(n)、変数を数個使うだけで済むため空間計算量 O(1) を満たします。ソート（O(n log n)）やハッシュセット（O(n) の追加メモリ）を使わずに済むため、メモリ制約が厳しい場面でも有効なアプローチです。