二重ループを使用してしまうと$O(n^2)$となるところを、ハッシュマップを使用して$O(n)$で計算できるようにします。
目次
二重ループによるtwo_sum
def two_sum(nums:list[int],T:int):
for i in range(len(nums)):
for j in range(len(nums)):
if i != j:
if nums[i] + nums[j] == T:
# print(nums[i],nums[j])
return True
return FalseHashMapによるtwo_sum
def two_sum_hashmap(nums:list[int],T:int):
hashMap : dict[int,int] = {i:T-i for i in nums}
for i in hashMap.keys():
if hashMap[i] in nums and hashMap[i] != i:
# print(hashMap[i],i)
return True
return False 検証
import random
for i in range(1000):
l,T = list(set([random.randint(0,100) for i in range(10)])),random.randint(0,100)
if not two_sum_hashmap(l,T) == two_sum(l,T):
print(two_sum_hashmap(l,T) )
print(two_sum(l,T))
print(l,T)
>>>
