CareerCup

This problem can be solved in O(n) time.

private static void findPairs(int[] a, int n){
		//map of the value of an element to the list of indices of elements equal to this one 
		Map<Integer, LinkedList<Integer>> indices = new HashMap<Integer,LinkedList<Integer>>();
		for (int i=0;i<a.length;i++){
			int pair = n-a[i];
			if (indices.containsKey(pair) && indices.get(pair).size() > 0){
				System.out.println(indices.get(pair).removeFirst() + " " + i);
			} else {
				if (!indices.containsKey(a[i]))
					indices.put(a[i], new LinkedList<Integer>());
				indices.get(a[i]).add(i);
			}
		}
	}

void sumTwo(int *arr, int size, int sum)
{
	int first, second;
	for(int i = 0; i < size; i++)
	{
		if(arr[i] <= sum)
		{
			first = arr[i];
			for(int j = i + 1; j < size; j++)
			{
        second = arr[j];
				if((second + first)==sum)
				{
					cout << first << " " << arr[j] << endl;
					int temp = arr[j];
					arr[j] = arr[i+1];
					arr[i+1] = temp;
					j = size;
          //i++;
				}
			}
		}
	}
}

for every element i in aray
For every element i search another element sum-i in array. ( o(n) for searching )

total complexity - o(n^2)
Can be reduced with fast searching algorithms)

Take element a[i] from i=1 to n from array and search a created binary tree of sum-a[i]. if a[i] matches we get a match else we add sum-a[i] to the tree.

The worse case complexity will be nlogn + nlogn = O(nlogn)

Famous and frequently asked question, the solution can be O(logN) + O(1).

sort it then traversing from both sides

without sorting can we just add the first element to all the elements one by one and store the values in the hash map,and the second with third and soon upto last element.till n-1 elemnts and store the values in the hash table.this hash table may need o(n(n-1)/2) time to construct but than the look up for any sum would be just o(1) times.
please,let me know if i am wrong.thanks in advance

1 build a BST , O(nlogn)

2. for i to sum, search sum-i, O(nlogn)

so O(nlogn)

Here is a Recursive version:

...
void FindSumOfPairs( int a[], int n, int sum )
{
	if( --n == 0 )
		return;
	FindSumOfPairs( &a[1], n, sum );
	for( int i = 0; i < n; i++ )
	{
		if( a[0] + a[i+1] == sum )
			cout << a[0] << "+" << a[i+1] << "=" << sum << endl;
	}
}
...
	int a[] = { 9, 6, -2, 1, -3, 7, -5 };
	int n = 7;
	FindSumOfPairs( &a[0], n, 4 );
...