Учитывая целочисленный массив nums, вернуть true, если какое-либо значение встречается не менее двух раз. в массиве и вернуть false, если все элементы различны.
Input: nums = [2 , 9 , 0, 4, 2] Output: true Input: nums = [1 , 9 , 0, 4, 2] Output: false Input: nums = [1 , 1] Output: true
Когда я читаю подсказку, первое, что приходит на ум, — использовать вложенный цикл for для сравнения каждого элемента друг с другом. Хотя этот подход определенно сработает, это решение грубой силы и не самое эффективное, когда речь идет о временной и пространственной сложности.
Пространственная сложность: O(n²) Временная сложность: O(1)
Другой подход будет включать сортировку списка и сравнение каждого элемента с элементом рядом с ним, используя 2 указателя. Этот подход экономит больше места, чем решение грубой силы.
Пространственная сложность: O(n*logn) Временная сложность: O(1)
Идеальным подходом было бы использование хэш-набора. Хэш-набор не может иметь дубликатов, идея состоит в том, чтобы перебирать массив и проверять, существует ли уже текущий элемент внутри набора. Если это так, верните True. Если нет, добавьте его в набор и продолжите цикл. Этот подход жертвует временем в обмен на пространство.
Пространственная сложность: O(n) Временная сложность: O(n)
class Solution:
def containsDuplicate(self, nums: List[int]) -> bool:
window = set()
for num in nums:
if num in window:
return True
window.add(num)
return False
