Hash table

O(n)

No hash table
O(nlogn)

How?? Can you please explain.

sort the array (nlogn)
i=0, j=n-1 (j is set to last element of the array)

then use following algo ( O(n))

while i<j
if( (arr[i] + arr[j]) > val)
j--;
else if( (arr[i] + arr[j]) < val)
i++;
else
print arr[i], arr[j]

I love it when people answer specific questions with data structures. Clearly shows they don't know what they are talking about. I have 7 solutions off the top of my head.

1.) Red black tree
2.) AVL tree
3.) Fibonnaci heap
4.) DAG
5.) DFA
6.) Stack
7.) Linear programming

1) Find the max, using a sort. nlog(n)
2) Populate a bit vector A[] with 1 for each integer in the array, 1 for those not in the array.
3) loop through the integer array, for each int i, if A[n-i]== 1. i and n-i are the two integers that add up to N.

There is no need to search in the 3rd step.

find min and max in O(n). then define a hash table with hashing function h(num)=num%d, where d=(max-min)/n.
now, for each element in an array search if the hash table contain a value (sum-num[i]) [i.e. search at the index h(sum-num[i])], if yes the present index and the number stored in hash table is the pair. If not, insert into hash table num[i].
Using this function, if we can assume that the numbers are uniformaly distributed, we can say that each bin will have one number on an avg. so the searching will be done in O(1). therefore total complexity is O(n).

could be done in On

	static void sumExists(int a[],int sum){
		Hashtable ht=new Hashtable();
		int tmp=0;
		int num1=0,num2=0;
		boolean exist=false;
		
		for (int i = 0; i < a.length; i++) {
			ht.put(i, i);
		}
		
		for (int i = 0; i < a.length; i++) {
			num1=a[i];
			tmp=sum-num1;
			if(ht.get(tmp)!=null){
				exist=true;
				num2=tmp;
				break;
			}
		}
		
		if(exist){
			System.out.println(num1+ "+"+num2+ " = "+sum);
		}
		else
			System.out.println("doest exist");
	}

Solution:
1. for each element in array add it to hashtable (HashSet in Java)
2. for each element in array, calculate sum-element, now lookup this value in the table. If it exists you're done

sort the array (nlogn)
i=0, j=n-1 (j is set to last element of the array)

then use following algo ( O(n))

while i<j
if( (arr[i] + arr[j]) > val)
j--;
else if( (arr[i] + arr[j]) < val)
i++;
else
print arr[i], arr[j]

This greedy algorithm is quite good.

---------
sort the array (nlogn)
i=0, j=n-1 (j is set to last element of the array)

then use following algo ( O(n))

while i<j
if( (arr[i] + arr[j]) > val)
j--;
else if( (arr[i] + arr[j]) < val)
i++;
else
print arr[i], arr[j]

This greedy algorithm is quite good.
-----------

This algo won't work. check it out.