Two Sum

Problem

Let’s take a look at the question,

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Click the above card to go to the problem on leetcode.

Approach

Think about what are the things we need to solve this a bit more efficiently.
By default we look straight at the nums list and start adding things to see what two elements when summed up give the value of the target.

It might seem easy in your head, but think about efficiency when trying to come up with an algorithm. Think how would an algorithm solve this.

One simple way is looking at one of the element from the list and subtracting that from the value of the target. Now check if that result exists in the list. Identify where it is located and return it’s index.

use enumerate to iterate over the list so you get both the value and the index

Remember to create a dictionary before you iterate. The dictionary should be populated like this - dict = {element - target: index value}

use hashmap to solve this now.

like we discussed above, get the difference between the element and the target.

if the difference exists in a dictionary or hashmap you created in the beginning, return the value pair and the current index we are at in the list.

If not, then we add the current element and its index to the hashmap.

Solution

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        dict = {}

        for i, n in enumerate(nums):
            diff = target - n
            if diff in dict:
                return [dict[diff], i]

            else:
                dict[n] = i

This question is categorized as easy.

When you look at the approach and the solution, you kinda see why it is.