Given an array of integers, return indices of the two numbers such that they add up to a specific target.

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

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1].

Solution

from typing import List, Dict

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

        for idx, num in enumerate(nums):
            dict[num] = idx
        for idx, num in enumerate(nums):
            idx2 = dict.get(target - num)
            if idx2 != idx and idx2 != None:
                return [idx, idx2]

        return []

Test Cases

test = Solution()
answer = test.twoSum([1,2,3,4], 6)
assert answer == [1,3]
answer = test.twoSum([1,7,3,3,4], 6)
assert answer == [2,3]
answer = test.twoSum([1,5], 6)
assert answer == [0,1]
answer = test.twoSum([-2**31,700, 1, 5, 45467, 94351231, 2**31-1, 456123197], -1)
assert answer == [0,6]
answer = test.twoSum([3,2,4], 6)
assert answer == [1,2]
print('All Passed!')

Big O Analysis

Space Complexity: O(N)

Time Complexity: O(N)