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)で済んでいる。