Find all pairs of integers within an array which sum to a specified value

Viewed 46569

Design an algorithm to find all pairs of integers within an array which sum to a specified value.

I have tried this problem using a hash table to store entries for the sum of array elements, but it is not an efficient solution.

What algorithm can I use to solve this efficiently?

15 Answers

Creating a hash table and then looking for value in it.

function sum_exist(num : number, arr : any[]) {
    var number_seen = {};
    for(let item of arr){
        if(num - item in number_seen){
            return true
        }
        number_seen[item] = 0;
    }
    return false;
}

Test case (using Jest)

test('Given a list of numbers, return whether any two sums equal to the set number.', () => {
    expect(sum_exist(17 , [10, 15, 3, 7])).toEqual(true);
});


test('Given a list of numbers, return whether any two sums equal to the set number.', () => {
    expect(sum_exist(16 , [10, 15, 3, 7])).toEqual(false);
});
#python 3.x
def sum_pairs(list_data, number):    
    list_data.sort()
    left = 0
    right = len(list_data)-1
    pairs = []
    while left < right:        
        if list_data[left]+list_data[right] == number:
            find_pairs = [list_data[left], list_data[right]]
            pairs.append(find_pairs)
            right = right-1
        elif list_data[left]+list_data[right] < number:
            left = left+1
        else:
            right = right-1
    return pairs
Related