Contains Duplicate

Problem

You are given an array of integers nums. Decide whether any value occurs more than once. Return True if some value appears at least twice, otherwise return False.

• The array is non-empty and has at most 200,000 elements.
• Each value fits comfortably in a 64-bit integer; magnitudes up to a billion are possible.

Examples

• nums = [4, 9, 2, 9, 5] → True, because 9 appears at indices 1 and 3.
• nums = [12, -3, 0, 7] → False, every value is distinct.
• nums = [42] → False, a single element cannot repeat.

Hints

1. The question is only "have I seen this value before?" for each element in turn.
2. Sorting would put equal values next to each other, but is there something faster than O(n log n)?
3. Walk the array once while inserting into a hash set; the first value already present is your answer.