0001. Two Sum

0001. Two Sum#

Problem#

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Examples#

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]

Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]

Constraints:#

2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
Only one valid answer exists.

Follow-up#

Can you come up with an algorithm that is less than \(O(n^2)\) time complexity?

Analysis#

  • If the array is sorted, we can easily find targets using two-pointer method/binary search.

  • The (index, value) pair related problem can be efficiently solved in \(O(n)\) time using hashing table.

    • iterate over the sequence

      • given index and value, find another set of (index, value)

Solution#

# Solution 1: naive solution O(n2)
def two_sum(nums, target):
    n = len(nums)
    for i, v in enumerate(nums):
        vnext = target - v
        for j in range(i+1, n):
            if nums[j] == vnext:
                return [i,j]
    return []
    
# test
nums = [2, 7, 11, 15] 
target = 9
print(two_sum(nums, target))

nums = [3, 2, 4]
target = 6
print(two_sum(nums, target))

nums = [3, 3]
target = 6
print(two_sum(nums, target))

nums = [0, 8, 7, 3, 3, 4, 2]
target = 11
print(two_sum(nums, target))

nums = [0, 1]
target = 1
print(two_sum(nums, target))

nums = [0, 2]
target = 3
print(two_sum(nums, target))

[0, 1]
[1, 2]
[0, 1]
[1, 3]
[0, 1]
[]

# Solution 2: hashing table O(n)
# The main idea here is since in the previous solution, the first loop has already iterated over the whole data set, there is no need to go through the data set in the inner loop agian. This could be done by using hashing table.
def two_sum(nums, target):
    tab = {}
    for i, v in enumerate(nums):
        vnext = target - v            
        if vnext not in tab:
            tab[v] = i
        else:
            return [tab[vnext], i]
    return []
    
# test
nums = [2, 7, 11, 15]
target = 9
print(two_sum(nums, target))

nums = [3, 2, 4]
target = 6
print(two_sum(nums, target))

nums = [3, 3]
target = 6
print(two_sum(nums, target))

nums = [0, 8, 7, 3, 3, 4, 2]
target = 11
print(two_sum(nums, target))

nums = [0, 1]
target = 1
print(two_sum(nums, target))

nums = [0, 2]
target = 3
print(two_sum(nums, target))

[0, 1]
[1, 2]
[0, 1]
[1, 3]
[0, 1]
[]
Contents