Two sum
July 10, 2022
array-and-hashmapProblem URL: Two sum
This problem has very clear statement. It will have a list of integer and a target integer. We should return the 2 indeces of the numbers that adds up to the target. It is guranteed that we will have a solution and it would be unique.
We can just through a hashmap into the problem and thats it. We will store the number itself as the key and index as the value in the hashmap. Then when we iterate over the whole list, we will check the complement that is target - current value
. If it is already exists in the hashmap, then we will return the index of the current element and also the index of the complement.
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
prevMap = {}
for i, n in enumerate(nums):
diff = target - n
if diff in prevMap:
return [prevMap[diff], i]
prevMap[n] = i
Time Complexity: O(n)
Space Complexity: O(n)