Find Two Numbers for a Sum

Given an array of integers, and a target integer, return indices of the two numbers that add up to the target number. This is a problem from leetcode at this link .

Solution: Naiive Solution

class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: for idi,i in enumerate(nums[:-1]): for idj,j in enumerate(nums[idi+1:]): if i+j==target: return [idi,idj+idi+1]

The above solution is still n^2 solution. Using a hashmap, we can craft a O(n) solution.

Solution: HashMap Solution

What we are going to do is create a dictionnary in python where we will insert elements that we already passed through. So for every new number we encounter, we first check if the complement is present in the dictionary. If it does, we have our answer

class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: my_dict = {} n = len(nums) for i in range(n): complement = target - nums[i] if complement in my_dict: # means the complement already exists, and we have saved the index of it return [i,my_dict[complement]] else: # if not, we save the number that we just visited my_dict[nums[i]] = i