CareerCup

public static void sumSearch(int[] a, int sum, int n) {
		for (int i = 0; i < n; i++) {
			for (int j = 1; j < n; j++) {
				if (a[i] + a[j] == sum) {
					System.out.println("The two elements with max sum are " + a[i] + " and "
							+ a[j]);
					return;
				}
			}
		}
		System.out.println("Items not found: No such element");
	}


Using Sorting

public static void sumSearchSort(int[] a, int sum, int n) {
		int i, j, temp;
		Arrays.sort(a);
		for (i = 0, j = n - 1; i < j;) {
			temp = a[i] + a[j];
			if (temp == sum) {
				System.out.println("The two elements with max sum are " + a[i] + " and "
						+ a[j]);
				return;
			} else if (temp < sum)
				i++;
			else
				j--;
		}
		System.out.println("Items not found: No such element");
	}

def two_sum(nums, target):
    all = set(nums)
    for num in nums:
        diff = target - num
        if diff in all:
            return (num, diff)
    return None

Sorting the list O(nlog(n)) + using Binary Search O(log(n)) = O(nlog(n))
Implementation in Python/3.6.1

def binary_search(l, number, i, j):
	if i >= len(l) or j < 0:
		return False
	if i == j and l[i] != number:
		return False
	mid = int((i + j) / 2)
	if l[mid] == number:
		return True
	if number <= l[mid]:
		return binary_search(l, number, i, mid - 1)
	return binary_search(l, number, mid + 1, j)

def find_numbers(ul, number):
	l = sorted(ul)
	min_ = l[0]
	end_index = len(l) - 1
	for i in range(min_, number - min_ + 1):
		if binary_search(l, i, 0, end_index) and binary_search(l, number - i, 0, end_index):
			return [i, number - i]
	return None

if __name__ == '__main__':
	unsorted_list = [10, 1, 3, 5, 2, 6, 11]
	number = 18
	print(find_numbers(unsorted_list, number))
	number = 5
	print(find_numbers(unsorted_list, number))

We can put the accessed items in a hash table for fast access. The total cost would be O(n log n).

#include <iostream>
#include <time.h> 
#include <algorithm>
#include <vector>
#include <unordered_map>

using namespace std;
const int nums = 100;
const int goal = 150;
const int mod  = 100;

int main()
{
	srand(time(0));
	vector<int> vec (nums);
	unordered_map<int, int> mpn;
 	int i = 0;
    	for(i = 0; i < nums; i++)
        vec[i] = rand() % mod;

    	for(i = 0; i < nums; i++)
    	{
    		if(mpn.count(goal - vec[i]) > 0)
    			cout << mpn[goal - vec[i]] << "  and  " << i <<  "  make the goal." << endl;
    		if(!mpn.count(vec[i]))
    			mpn[vec[i]] = i;
    	}
}

The fastest solution: O(N).
Loop the array and keep each number visited in an hash table. For each number in the array check the hash if we have in the hash sum-currentnumber, if we do, we are done.

std::pair<int, int> findNumbersSumEqual(const std::vector<int>& numbers, int sum)
{
    std::unordered_set<int> visited;
    for(size_t i=0; i<numbers.size(); ++i) {
        // search the diff in the map
        int secondNumber = sum - numbers[i];
        if(visited.count(secondNumber)) {
            // we already saw this number before in the array
            return {numbers[i], secondNumber};
        } else {
            // Keep this number in the hash
            visited.insert(numbers[i]);
        }
    }
    return {INT_MAX,INT_MAX}; // No match was found
}

"""
return list of tuples with items in list that add to a sum
"""
def twoSum(list, sum):
    s = set(list);
    result = []
    for i in list:
        diff = sum - i
        if diff in s:
            result.append  (tuple ([i, diff]) )
    return result


list = [1, 2, 3, 4, 5, 6, 9]
result = twoSum(list, 9)
print(result)