1_Two Sum

[easy] [array, hash table]

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 1: brute force

• Fix the position of the first number, and search for the second number that satisfy the condition.

Time Complexity: $O(n^2)$

Space Complexity: $O(1)$

def twoSum(nums, target):
    """
    :type nums: List[int]
    :type target: int
    :rtype: List[int]
    """
    for i in range(len(nums)-1):
        for j in range(i+1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]

Solution 2: sort + two pointers

• Sort the numbers first, then use two pointers to find the pair.

Time Complexity: $O(n log(n))$

Space Complexity: $O(1)$

def twoSum(nums, target):
    nums = enumerate(nums)
    nums = sorted(nums, key=lambda x:x[1])
    i, j = 0, len(nums)-1
    while i < j:
        if nums[i][1] + nums[j][1] == target:
             return sorted([nums[i][0], nums[j][0]])
        elif nums[i][1] + nums[j][1] < target:
            i += 1
        else:
            j -= 1

def twoSum(nums, target):           
    dic = {}
    for i, num in enumerate(nums):
        dic[num] = dic.get(num, []) + [i]
    nums.sort()
    left, right = 0, len(nums) - 1
    while left < right:
        tmp = nums[left] + nums[right]
        if tmp == target:
            if len(dic[nums[left]]) == 2:
                return [dic[nums[left]][0], dic[nums[right]][1]]
            return [dic[nums[left]][0], dic[nums[right]][0]]
        if tmp > target:
            right -= 1
        elif tmp < target:
            left += 1

Solution 3: dictionary

• Check elements in the array one by one. Use a dictionary to store information for future checking of the next element.Key is target - element. Value is the index. Such that for every next element, search if it exists in the dictionary.If it does, return the value we find and the index for current element. Otherwise add new key-value pair into the dictionary.

• The key point is to use dictionary instead of array. Searching in dictionary is O(1). Searching in arrary is O(n).

Time Complexity: $O(n)$

Space Complexity: $O(n)$

def twoSum(nums, target):
    dic = {}
    for i in range(len(nums)) :
        if nums[i] in dic :
            return [dic.get(nums[i]), i]
        else :
            dic[target-nums[i]] = i