How to solve the two-sum problem
Problem statement
Find all the pairs of numbers in an unsorted array arr that sum to a given number target.
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.
Solution statement
There can be two approaches to solve this problem:
- Naive approach
- Efficient approach
1. Naive approach
The Naive approach would be to choose an element (e) from 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.
Code
Example 1
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 resdef main ():arr = [3, 5, 2, -4, 8, 11]target = 7print(twoSum(arr, target))main()
2. Efficient approach
We can efficiently solve this problem using sets. We can add every element of arr if the target - arr[i] value exists in the sums set.
This implies that target = arr[i] + (the value in sums), which this will be a solution. This algorithm will run in .
Example 2
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 resdef main ():arr = [3, 5, 2, -4, 8, 11]target = 7print(twoSum(arr, target))main()
