Two Sum

leetcode

Native method

def twoSum(self, nums: List[int], target: int) -> List[int]:
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]
    return []

• where we wasted most time? we try to access the data in the list in every loop, so we can use a dictionary to store the data and access it in O(1) time.
• use hashmap

Hashmap

def twoSum(self, nums: List[int], target: int) -> List[int]:
    seen_map = {}
    for i in range(len(nums)):
        num = nums[i]
        if target - num in seen_map:
            return [seen_map[target-num], i]
        seen_map[num] = i
    return []