easyArraysPattern: Math
Sum of Pairs Solution
Problem Statement
Given an array of integers, find all pairs that sum to a given target value.
Examples
Example 1:
Input:[1, 2, 3, 4, 5, 6]
Output:[]
Explanation: These pairs sum to 6, which is the target value for this example. The target value should be given, the provided example does not contain it.
Example 2:
Input:[-1, 0, 3, 4, 5, 6]
Output:[]
Explanation: This pair sums to 3, which should be the target value for this example.
Example 3:
Input:[10, 20, 30, 40, 50]
Output:[]
Explanation: This pair sums to 50, which should be the target value for this example.
Constraints
- Input array can have negative numbers.
- Input array can have duplicate numbers.
- Input array can have zero.
- Target value can be zero.
- Array can be empty.
Time: O(n) Space: O(n)
An optimized approach would use a hash map to store the elements and their indices, and then use two pointers to iterate through the array and find all pairs that sum to the target value with a time complexity of O(n).
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
def sum_of_pairs(arr, target): m = {} for i in range(len(arr)): if target - arr[i] in m: return [m[target - arr[i]], i] m[arr[i]] = i return []