Find all the pairs of numbers in an unsorted array
arr that sum to a given number
For example, if the array is
[3, 5, 2, -4, 8, 11] and the sum is
7, your program should return
[[11, -4], [2, 5]] because
11 + -4 = 7 and
2 + 5 = 7.
There can be two approaches to solve this problem:
The Naive approach would be to choose an element (
arr and loop through the rest of it to see if the sum of (
e) and some other element equals the target.
However, this will result in the time complexity of , which is inefficient.
The Python program below implements the algorithm using the Naive approach:
def twoSum (arr, target): res =  for i in range(len(arr)): for j in range(i, len(arr)): if arr[i] + arr[j] == target: res.append([arr[i], arr[j]]) return res def main (): arr = [3, 5, 2, -4, 8, 11] target = 7 print(twoSum(arr, target)) main()
We can efficiently solve this problem using sets. We can add every element of
arr if the
target - arr[i] value exists in the
This implies that
target = arr[i] + (the value in sums), which this will be a solution. This algorithm will run in .
def twoSum (arr, target): res =  sums = set() for val in arr: if target - val in sums: res.append([val, target - val]) sums.add(val) return res def main (): arr = [3, 5, 2, -4, 8, 11] target = 7 print(twoSum(arr, target)) main()
View all Courses