Interview challenge · easy · array, hash-set
Contains Duplicate
El reto
El enunciado va en inglés, igual que en el vídeo.
Given an integer array nums, return true if any value appears at least twice, and false if every element is distinct.
Example
[1, 2, 3, 1] -> true
[1, 2, 3, 4] -> false
[1, 1, 1, 3, 3, 4, 3, 2, 4, 2] -> trueIdea: remember what you have seen in a hash set; the first number already in the set is a duplicate. Time O(n), space O(n). In C, sorting first and comparing neighbours gives O(n log n) with no extra memory.
La solución
# Contains Duplicate - ayotl.dev
def contains_duplicate(nums):
seen = set() # O(1) lookups
for n in nums:
if n in seen:
return True # seen it before
seen.add(n)
return False
print(contains_duplicate([1, 2, 3, 1]))
print(contains_duplicate([1, 2, 3, 4]))
$ python3 contains_duplicate.py
True
False