速い指と遅い指で並びの中の重なった数を探す

連結リスト問題 89

1 から n までの数が n + 1 個入った並びから、2 回以上出てくる数を、並びを書き換えず O(1) の記憶で返します。値を次の行き先と見て連結リストの輪を探す練習です。

海外で定番の問題リスト 4 本には入っていません

問題

整数の並び nums を受け取ります。要素の数は n + 1 個で、どの値も 1 以上 n 以下です。2 回以上出てくる値はちょうど 1 種類あります。その値を返す関数を書いてください。

重なった値は 2 回とは限らず、3 回以上出てくることもあります
nums を書き換えてはいけません (並べ替えも、印を付けるのも無しです)
使う記憶は O(1) にしてください。集合や数を数える表は使えません
n は 1 以上 10000 以下です

入力と出力の例

例 1

座席の番号札 1 から 5 を 6 人に配ったら、同じ番号が 2 枚混ざっていました。4 番が 2 回出てきます。

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

例 2

重なった値が 3 回以上出てくることもあります。2 が 4 回出てきます。

nums = [2, 2, 2, 1, 2]

例 3

いちばん小さい n です。2 個とも 1 です。

nums = [1, 1]

面接での聞かれ方

条件を足していくと解き方が変わる問題として、ミドルの面接で出ます。

「重なった数を探してください」とだけ聞かれ、集合で解くと「記憶を O(1) にできますか？」「並びを書き換えずに？」と条件を足されます
並べ替える、値の位置に負の印を付ける、という答えは「書き換えない」で外されます
値の範囲で二分探索する O(n log n) の書き方を答えると、「O(n) にできますか？」と続くことがあります

ミドルの問題なので、並びを連結リストと見なす発想と、輪の入口を見つける 2 段目の理由を説明できるかが見られます。

ヒント

まだ開いていません

付箋は 4 枚。下の段ほど答えに近づきます

ヒント 2
ヒント 3
ヒント 4答えに近い

アルゴリズムのチートシートの「配列と文字列」に、この型の要点を表とコードでまとめています。

配列と文字列の問題は、全部の組を調べると手間が大きくなる所を、窓や左右の添字で減らす形が多いです。

まず考える手順

段 1

まずは素直に、見た値を集合に入れ、2 回目に見た値を返す書き方を考えます。O(n) で動きますが、記憶を O(n) 使います。並べ替えれば記憶は減りますが、並びを書き換えます。

段 2

番号 i の要素 nums[i] を「i の次は nums[i] へ行く」と読みます。どの値も 1 以上 n 以下なので、0 番から出発して行き先をたどり続けられ、0 番には誰も戻ってきません。n + 1 個の番号を n 個の値に向けるので、2 つの番号から同じ所へ来る場所が必ずあり、そこが輪の入口です。輪の入口の番号が、重なった値です。

段 3

連結リストの輪を見つけるときと同じく、1 歩ずつ進む遅い指と、2 歩ずつ進む速い指を 0 番から出します。輪に入ると、速い指がいずれ遅い指に追いつきます。

段 4

出会ったら、片方の指を 0 番に戻し、両方を 1 歩ずつ進めます。もう一度出会った所が輪の入口です。出発点から入口までの歩数と、出会った所から入口までの歩数が、輪の周を除いて同じになるからです。

解答

Python

def find_duplicate(nums):
    slow = nums[0]
    fast = nums[nums[0]]
    while slow != fast:
        slow = nums[slow]
        fast = nums[nums[fast]]
    slow = 0
    while slow != fast:
        slow = nums[slow]
        fast = nums[fast]
    return slow

JavaScript

function findDuplicate(nums) {
  let slow = nums[0];
  let fast = nums[nums[0]];
  while (slow !== fast) {
    slow = nums[slow];
    fast = nums[nums[fast]];
  }
  slow = 0;
  while (slow !== fast) {
    slow = nums[slow];
    fast = nums[fast];
  }
  return slow;
}

Go

func findDuplicate(
	nums []int,
) int {
	slow := nums[0]
	fast := nums[nums[0]]
	for slow != fast {
		slow = nums[slow]
		fast = nums[nums[fast]]
	}
	slow = 0
	for slow != fast {
		slow = nums[slow]
		fast = nums[fast]
	}
	return slow
}

最初の繰り返しの前に 1 歩と 2 歩を進めておくのは、両方を 0 番に置いたままだと、出発した時点で「出会った」ことになるからです。

計算量

時間は O(n) です。速い指が遅い指に追いつくまでと、入口までもう一度歩く所が、どちらも n の数倍の歩数で済みます
使う記憶は O(1) です。指 2 本だけで、並びは読むだけです

よくある間違い

出会った所の値を答えにする。出会う所は輪の中のどこかで、入口とは限りません。nums = [2, 4, 3, 1, 3] では、遅い指と速い指は 1 番で出会いますが、答えは 3 です。2 段目の歩きが要ります
2 段目で、もう片方も 0 番に戻す。戻すのは片方だけです。もう片方は出会った所から歩かせます
番号と値を取り違える。指が持つのは番号で、次の番号は nums[今の番号] です。最後に返すのは、入口の番号 (それが重なった値) です
並べ替えて隣を比べる。動きますが、並びを書き換えるので条件に合いません

解答を動かした版 Python 3.14.7Node.js 24.22.1Go 1.24.2確認日 2026年11月8日

main.py

def find_duplicate(nums: list[int]) -> int:
    """
    Goal: 何を返すか

    idea1: まず思いつく案
    -> runtime: O(?)  space: O(?)

    idea2: もっと速い案
    -> runtime: O(?)  space: O(?)

    edge case: 空、1 つだけ、など
    """
    # ここに書きます
    pass


# 「実行」を押すと、この行の結果が出ます
print(find_duplicate([3, 4, 1, 5, 4, 2]))

できているか「例で確かめる」を押すと、問題の例を全部この関数に渡して、通ったかをここに出します