1. Two Sum

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.

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Output: 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 <= 10³
-10⁹ <= nums[i] <= 10⁹
-10⁹ <= target <= 10⁹
Only one valid answer exists.

Source

Code

In [1]:

def two_sum(nums, target):
    comp_set = {}
    for index, number in enumerate(nums):
        if target - number in comp_set:
            return [comp_set[target-number], index]
        comp_set[number] = index

Check

In [2]:

nums = [2, 7, 11, 15]
target = 9

two_sum(nums, target)

Out[2]:

[0, 1]

In [3]:

nums = [3, 2, 4]
target = 6

two_sum(nums, target)

Out[3]:

[1, 2]

In [4]:

nums = [3, 3]
target = 6

two_sum(nums, target)

Out[4]:

[0, 1]

In [5]:

nums = [1, 2, 3, 1]
target = 3

two_sum(nums, target)

Out[5]:

[0, 1]

Follow up #1:

Handle the case where there are multiple pairs possible with the following conditions:

an element can only be used a single time
an element can be used several times

Code

In [6]:

def two_sum(nums, target):
    """An element can only be used once."""
    comp_set = {}
    valid_pairs = []
    for index, number in enumerate(nums):
        if (target - number) not in comp_set:
            if number in comp_set:  # but if duplicate elements
                comp_set[number].append(index)
            else:
                comp_set[number] = [index]
        else:
            valid_pairs.append([comp_set[target-number].pop(), index])  # pop one of the duplicate
            if comp_set[target-number] == []:
                del comp_set[target-number]            
    return valid_pairs

In [7]:

def two_sum(nums, target):
    """An element can be used multiple times."""
    comp_set = {}
    valid_pairs = []
    for index, number in enumerate(nums):
        if (target - number) not in comp_set:
            if number in comp_set:  # but if duplicate elements
                comp_set[number].append(index)
            else:
                comp_set[number] = [index]
        else:
            for duplicate in comp_set[target-number]:  # loop over the duplicates
                valid_pairs.append([duplicate, index])
    return valid_pairs

Check

In [8]:

nums = [1, 1, 3, 2, 2]
target = 4

two_sum(nums, target)

Out[8]:

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

In [9]:

nums = [1, 2, 3, 4, 5, 13, 14, 11, 13, -1, 9, 8, 7, 6]
target = 10

two_sum(nums, target)

Out[9]:

[[7, 9], [0, 10], [1, 11], [2, 12], [3, 13]]

Follow up #2:

Return the pairs of integer instead of their indexes (multiple pairs possible). Handle the following conditions:

an element can only be used a single time
an element can be used several times

Code

In [10]:

def two_sum(nums, target):
    '''Using set(). An element can only be used only once.'''
    comp_set = set(nums)
    valid_pairs = []
    for number in comp_set:
        if ((target - number) in comp_set
           and (number, target-number) not in valid_pairs
           and (target-number, number) not in valid_pairs):
            valid_pairs.append((number, target-number))
    return valid_pairs

In [11]:

def two_sum(nums, target):
    """An element can only be used once."""
    comp_set = {}
    valid_pairs = []
    for index, number in enumerate(nums):
        if (target - number) not in comp_set:
            if number in comp_set:  # but if duplicate elements
                comp_set[number].append(index)
            else:
                comp_set[number] = [index]
        else:
            valid_pairs.append([target-number, number])  # pop one of the duplicate
            if comp_set[target-number] == []:
                del comp_set[target-number]            
    return valid_pairs

In [12]:

def two_sum(nums, target):
    """An element can be used multiple times."""
    comp_set = {}
    valid_pairs = []
    for index, number in enumerate(nums):
        if (target - number) not in comp_set:
            if number in comp_set:  # but if duplicate elements
                comp_set[number].append(index)
            else:
                comp_set[number] = [index]
        else:
            for duplicate in comp_set[target-number]:  # loop over the duplicates
                valid_pairs.append([target-number, number])
    return valid_pairs

Check

In [13]:

nums = [1, 1, 3, 2, 2]
target = 4

two_sum(nums, target)

Out[13]:

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

In [14]:

nums = [1, 2, 3, 4, 5, 13, 14, 11, 13, -1, 9, 8, 7, 6]
target = 10

two_sum(nums, target)

Out[14]:

[[11, -1], [1, 9], [2, 8], [3, 7], [4, 6]]