How to write an algorithm to check if the sum of any two numbers in an array/list matches a given number?

I'm sure there's a better way, but here's an idea:

1. Sort array
2. For every element e in the array, binary search for the complement (sum - e)

Both these operations are O(n log n).

This can be done in O(n) using a hash table. Initialize the table with all numbers in the array, with number as the key, and frequency as the value. Walk through each number in the array, and see if (sum - number) exists in the table. If it does, you have a match. After you've iterated through all numbers in the array, you should have a list of all pairs that sum up to the desired number.

array = initial array
table = hash(array)
S = sum

for each n in array
    if table[S-n] exists
        print "found numbers" n, S-n

The case where n and table[S-n] refer to the same number twice can be dealt with an extra check, but the complexity remains O(n).

Use a hash table. Insert every number into your hash table, along with its index. Then, let S be your desired sum. For every number array[i] in your initial array, see if S - array[i] exists in your hash table with an index different than i.

Average case is O(n), worst case is O(n^2), so use the binary search solution if you're afraid of the worst case.