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 + nums = 2 + 7 = 9,
return [0, 1].

Solution in Python

1. Approach 1: Brute Force

class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
for i, a in enumerate(nums):
diff = target - a
for j, b in enumerate(nums[i+1:]):
if diff == b:
return [i, i+1+j]

Complexity Analysis

• Time complexity : O(n2). For each element, we try to find its complement by looping through the rest of array which takes O(n). Therefore, the time complexity is O(n2).
• Space complexity: O(1).

2. Approach 2: One-pass Hash Table

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

Complexity Analysis

• Time complexity: O(n). We traverse the list containing n elements only once. Each look up in the table costs only O(1) time.
• Space complexity : O(n). The extra space required depends on the number of items stored in the hash table, which stores at most n elements.