集合で同じ値が 2 回出てくるかを確かめる

配列とハッシュ問題 07

整数の並びの中に、同じ値が 2 回以上出てくるかを判定します。見た値を集合に覚え、出てきた値がもう集合にあるかを一定の手間で調べる練習です。

海外で定番の問題リスト 4 本のうち 3 本に入っています (Blind 75、NeetCode 150、Grind 75)

問題

整数の並び nums を受け取ります。nums の中に、同じ値が 2 回以上出てくるなら真、どの値も 1 回しか出てこないなら偽を返す関数を書いてください。

位置が違っても値が同じなら、同じ値とみなします。5 と -5 は別の値です
nums の長さは 1 以上 100000 以下、値はどれも絶対値が 10 億以下です

入力と出力の例

例 1

nums = [4, 9, 2, 9, 7]

true

例 2

nums = [15, -3, 8, 0]

false

例 3

同じ値が離れた位置にあっても、見つけられる必要があります。

nums = [-7, 7, 0, 3, -7]

true

面接での聞かれ方

面接の最初の 1 問として、短く出されることが多い問題です。

「整数の配列に重複があるかを返してください」
書き終えたあとに「計算量は？」「メモリを使わずに解くとどうなりますか？」と、時間と記憶の取り引きを聞かれます
「重複が見つかったら、すぐに止められますか？」と、早く打ち切れるかを聞かれることもあります

答えは真か偽だけなので、すぐに書けます。そのぶん、ほかの書き方と比べて計算量を言えるかが見られています。

ヒント

まだ開いていません

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

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

アルゴリズムのチートシートの「ハッシュマップ」に、この型の要点を表とコードでまとめています。

ハッシュは、値から番地を計算して、探す手間をほぼ 1 回にする仕組みです。重複や回数の問題は、この形で解けます。

まず考える手順

段 1

まずは素直に、2 つの組を全部比べる書き方を考えます。2 重の繰り返しで、ある位置の値とそれより後ろの値を全部比べれば答えは出ます。ただ、長さが 100000 なら比べる回数は約 50 億回になり、間に合いません。

段 2

並べ替えると、同じ値は必ず隣り合います。並べ替えたあと、隣どうしを 1 回ずつ比べれば足ります。時間は並べ替えの O(n log n) で、元の並びを並べ替えてよいなら記憶はほとんど要りません。

段 3

さらに速くするには、集合 (Python の set、JavaScript の Set、Go では値を鍵にした map) を使います。前から 1 つずつ見て、その値がもう集合にあれば重複です。無ければ集合に足して次へ進みます。集合を調べるのも足すのも平均して一定の手間なので、並びを 1 回なめるだけで済みます。

解答

Python

def has_duplicate(nums):
    seen = set()
    for x in nums:
        if x in seen:
            return True
        seen.add(x)
    return False

JavaScript

function hasDuplicate(nums) {
  const seen = new Set();
  for (const x of nums) {
    if (seen.has(x)) {
      return true;
    }
    seen.add(x);
  }
  return false;
}

Go

func hasDuplicate(
	nums []int,
) bool {
	seen := map[int]bool{}
	for _, x := range nums {
		if seen[x] {
			return true
		}
		seen[x] = true
	}
	return false
}

重複が見つかったところで、残りを見ずに真を返します。最後の行に来るのは、全部の値を見ても重複が無かったときだけです。

計算量

時間は O(n) です。並びを前から 1 回なめ、集合を調べるのも足すのも、平均して一定の手間で済みます
使う記憶は O(n) です。重複が無いときは、全部の値を集合に覚えます
段 2 の並べ替えの書き方は、時間が O(n log n) で、元の並びをその場で並べ替えるなら記憶は O(1) に近くなります。記憶を使う代わりに時間を縮めた、という取り引きです

よくある間違い

並びを集合に変えて長さを比べるだけにする。 len(set(nums)) != len(nums) も正しく動きますが、重複が先頭にあっても全部の値を集合に入れ終わるまで止まりません。「すぐに止められますか？」と聞かれたら、1 つずつ足す書き方に直せるようにしておきます
並べ替えの書き方で、元の並びを黙って並べ替える。呼んだ側の並びが変わってしまいます。並べ替えてよいかを面接官に確かめるか、写しを作って並べ替えます (写しを作るなら記憶は O(n) です)
先に集合へ足してから調べる。 seen.add(x) を if より前に置くと、いま足したばかりの自分を見つけて、どの並びでも最初の値で真を返します。「調べてから足す」の順を守ります

解答を動かした版 Python 3.12.14Node.js 22.23.4Go 1.24.6確認日 2026年10月30日

main.py

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

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

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

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


# 「実行」を押すと、この行の結果が出ます
print(has_duplicate([4, 9, 2, 9, 7]))

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