You are given a list of integers nums.
Return true if some value appears at least twice in nums, and false if every value is
different.
Example 1
- Input
- nums = [4, 1, 7, 1]
- Output
- true
1 appears at positions 1 and 3.Example 2
- Input
- nums = [3, 8, -2, 5]
- Output
- false
All four values are different.
Constraints
numsholds 1 to 10⁵ numbers.- Every number is between −10⁹ and 10⁹.
Show the pattern
Hashing
For each number you need to know whether you have met it before. A hash set answers "seen it?" in constant time, so one pass is enough.
See hashing in a visualiserShow the approach
Walk through the list once with an empty hash set. For each number, if it is already in the set,
you have found a repeat: return true. Otherwise add it and move on. If the walk ends, every
number was new, so return false.
Comparing the size of set(nums) with the length of the list gives the same answer in one line,
but the loop can stop at the first repeat.
Time: O(n) · Space: O(n)
Brush up firstHash Set visualiser