CareerCup

As mentioned by Ayush, if there are no space constraints, a "map/hashtable" can do the job in O(n) where "n" is the length of the list (in fact the number of distinct numbers on the list). I added a simple java function for that.

public static void Solve(Iterator<Integer> numbers, int K) {
        HashMap<Integer, Integer> table = new HashMap<>();
        while (numbers.hasNext()) {
            Integer new_number = numbers.next();            
            table.put(new_number, K - new_number);
            int target = K - new_number;
            if (table.containsKey(target)) {
                System.out.print("Found the pair (" + new_number.toString() + 
                        ", " + Integer.toString(target) + ")\n");
            }            
                
        }
    }

Example:

public static void main(String[] args) {
        // TODO code application logic here
        List<Integer> l = new LinkedList<>();
        for (int i = 1; i < 21; i++)
            l.add(i);
        SumKonLL.Solve(l.iterator(), 13);
                
    }

Output:

Found the pair (7, 6)
Found the pair (8, 5)
Found the pair (9, 4)
Found the pair (10, 3)
Found the pair (11, 2)
Found the pair (12, 1)

public static void findPair(int [] array , int k){
		HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
		
		for (int i =0 ; i<array.length;++i){
			if (map.containsKey(array[i])){				
				System.out.println(map.get(array[i])+ " : " + array[i]);
			}else{
				map.put(k-array[i], array[i]);
			}
		}

}

use a hashtable

time complexity O(n)
space complexity O(MAX(list)-MIN(list)+1)

//suppose that integer is 5
		LinkedList<Integer>test=new LinkedList<Integer>();
		//adding some elements
		test.add(1);
		test.add(2);
		test.add(4);
		test.add(3);
		test.add(6);
		test.add(5);
		for (Integer no1 : test) {
			if(test.contains(5-no1))
				System.out.println("OUTPUT:"+no1+" "+(5-no1));
		}

Previous answer is O(n^2). This one is O(n*logn), assuming that find a number in a set takes logN.

void findPair(list<int> aList, int sum)
{
	set<int> aSet;

	for each (auto item in aList)
	{
		if (aSet.find(sum - item) != aSet.end())
		{
			cout << item << " " << (sum - item) << endl;
		}
		aSet.insert(item);
	}

}

How about converting the array to a BST and then for a node(say root node) in the bst search for some other node(say target node) whose value when added with the reference node will give the desired sum. Now delete the reference node and target node . Continue this process untill last 2 nodes are present. Every search will happen in O(log m) where m is number of elements in BST. With each iteration value of m will decrease by a factor of 2 as we will delete the reference node. If space is not a constraint then we can improve the results further by using DP.

In Python:

def findSumToK(L, k):

    map = {}

    node = L.head
    while node:
        map[node.data] = node
        node = node.next

    node = L.head
    while node:
        i = k - node.data
        if map.get(i):
            return map.get(i), node
        node = node.next