Two Sum

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

Solution 1:

def twoSum(nums, target):
    """
    :type nums: List[int]
    :type target: int
    :rtype: List[int]
    """
    for i in range(len(nums)):
        if target - nums[i] in nums and nums.index(target - nums[i]) != i:
            return [i, nums.index(target - nums[i])]

time complexity: O(n^2) 因为loop每一个number需要花O(n), 然后再loop他们的complement同意需要O(n), 所以是O(n^2)

Solution 2:

def twoSum(nums, target):
    """
    :type nums: List[int]
    :type target: int
    :rtype: List[int]
    """
    lookup = {}     
    for i, num in enumerate(nums):
        if target - num in lookup:
            return [lookup[target-num], i]
        lookup[num] = i 

time complexity: O(n)