# Challenge: Target Sum

### Question:

Find two indexes from a list whose values are summed up to a predefined target number.

• Input: A list of integers and a target number.
• Output: another list containing two (or a pair of) indexes of the input list whose values summed up to the target number. If such pair does not exist, return None. If there exists many such pairs, output one of them.

An example:

• Input
• array: [2, 0, 1, 6, 8, 9]
• target number: 7
• Output: [2, 3]
• Explanation: The two numbers that summed up to 7 are 1 and 6 and they are the second and the third element of the array input.

A brute force solution with O(n2) complexity:

``````def target_sum(arr_int, target):
for i in range(len(arr_int)):
for j in range(i+1, len(arr_int)):
if arr_int[i]+arr_int[j] == target:
# found, return the index pair
return [i,j]
return None``````

A faster solution with O(n) complexity, using a hash map:

``````def faster_target_sum(arr_int, target):
remainders = {}
for i in range(len(arr_int)):
if arr_int[i] in remainders:
# found, return the index pair
return [remainders[arr_int[i]], i]
else:
# not found yet, added the remainder to the hash map
remainder = target - arr_int[i]
remainders[remainder] = i