Two Sum

Hash Table
Easy

Approach

Iterate down

nums

once. For each

num

in

nums

, calculate

otherNum

that sums to

target

. Then check if

otherNum

is in

hashmap

. If yes, we have our two numbers and can return their indices. If no, add

num

and

idx

to

hashmap

and continue.

Diagrams

Analysis

Time

O(n)

Space

O(n)
from collections import defaultdict


def twoSum(nums, target):
    hashmap = defaultdict(int)

    for idx, num in enumerate(nums):
        otherNum = target - num

        if otherNum in hashmap:
            otherIdx = hashmap[otherNum]
            return [idx, otherIdx]

        hashmap[num] = idx

Learn

#Hash Table

Videos