Почему HashSet быстрее, чем Array в этой проблеме с повторяющимися целыми числами?

Я новичок в изучении структур данных и алгоритмов и начинаю решать задачи NeetCode 150. Первая проблема, с которой я столкнулся, была несложной, я понимаю, почему она работает, но мне любопытно, почему лучшее решение предполагает использование HashSet вместо массива.

Я уверен, что речь идет о временной сложности, а это тема, которую мне трудно понять, поэтому я надеюсь, что кто-нибудь сможет дать мне простое объяснение, почему одно решение лучше другого, и будет ли оно действительно таковым. плохо использовать здесь массив вместо HashSet (если бы я использовал его в интервью, им бы это не понравилось).

Это решение, которое я придумал. Он практически идентичен, за исключением использования массивов и .append() вместо HashSet и .add(). Решение было технически правильным, но, судя по проведенным мной исследованиям, решение HashSet оказалось лучше/быстрее, и мне нужна помощь, чтобы понять, почему.

class Solution:
    def hasDuplicate(self, nums: List[int]) -> bool:
        newArray = []
        for i in nums:
            if i in newArray:
                return True
            newArray.append(i)    
        return False

Вот самое лучшее решение.

class Solution:
    def hasDuplicate(self, nums: List[int]) -> bool:
        hashset = set()

        for n in nums:
            if n in hashset:
                return True
            hashset.add(n)
        return False

В чем различия? Также какое влияние окажет добавление nums.sort() на первый подход? Изменит ли это каким-либо образом время выполнения? Извините, если эти вопросы до боли очевидны, мне просто нужна помощь, чтобы разобраться в этих концепциях.