LeetCode 217. Contains Duplicate

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        dic = dict()
        for num in nums:
            if num not in dic.keys():
                dic[num] = True
            else:
                return True
        return False

その数字が最初に出てくるインデックスを返すindex()を用いて
nums.index(nums[i])
とiが等しいかを調べようとしたらtime limit exceedした。

index()は配列を先頭から全部見る必要があるので計算量がO(n)かかる
なので、全体としてはO(n^2)の計算時間がかかってしまう。

辞書型を使うことで過去に出てきた数字かどうかを確認するのにO(1)で済むので、
全体の計算量としてはO(n)で済んでいる。