# LeetCode--TwoSum
# 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].
'''

def twoSum(nums, target):
    """
    :type nums: List[int]
    :type target: int
    :rtype: List[int]
    """
    # Create dictionary(hash map) to store d[array_value] = its index
    # If multiple values are the same, append its index to d[array_val]
    # Complexity: O(n)
    d = {}
    for i in range(len(nums)):
        if nums[i] not in d.keys():
            d[nums[i]] = [i]
        else:
            d[nums[i]].append(i)

    # Loop through d --> O(n)
    for k, v in d.items():
        # Retrieve the missing part of the sum if exists in d --> O(1)
        if (target - k) in d.keys():
            # In case of using two identical values to sum
            if len(v) > 1 and (target-k) == k:
                return [v[0], v[1]]
            else:
                return [v[0], d[target-k][0]]