Problem

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

# Solution:
# The solution below is optimal because it uses a dictionary to store the values of the array.
# The dictionary is used to check if the complement of the current value is in the dictionary.
# If it is, then the indices of the complement and the current value are returned.
# The time complexity of this solution is O(n) because the dictionary is iterated through once.
# The space complexity of this solution is O(n) because the dictionary is the same size as the array.

def twoSum(nums, target):
    """
    :type nums: List[int]
    :type target: int
    :rtype: List[int]
    """
    d = {}
    for i in range(len(nums)):
        complement = target - nums[i]
        if complement in d:
            return [d[complement], i]
        d[nums[i]] = i
    return []