Intuition

Keep a hash map of numbers and it’s indexes: hashmap[num] = index

Approach

Calculate the complement (target - num[i]). if complements exists in hashmap, return indexes if not, add the current number the the hashmap hashmap[num] = index.

Complexity

  • Time complexity: O(n)

  • Space complexity: O(n)

Code

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        
        m = len(nums)
        r = range(m)

        compl = {}

        for i in r:            
            complement = target - nums[i]

            if complement in compl:
                return [i, compl[complement]]
            
            compl[nums[i]] = i
        
        return []