CareerCup

Sort. Traverse from either ends.

Hashing would work in O(n).

What hashing

sort O(nlogn)
now start from both ends

target_sum(int a[n],int target)
{
qsort(a);//sorting :P
int i,j;
i=0; j=n-1;
sum=0;
while(i<=j)
{
sum=a[i]+a[j];
if(sum==target) {cout<<a[i]; cout<a[j]; break;}
else if(sum<target) i++;
else if(sum>target) j--;
}
return
}

Hashing would work in the following way...
insert all the elements of the array in the hashtable..this takes O(n) time
now for each element a[i] in the array check whether targetNumber - a[i] exists in the hashtable. this takes O(n) time
totally TC = O(n+n) = O(n)..

sort the array. pick first number, subtract it from target and binary search for (Target-firstNum) in A[2...N], then pick A[2] and binary search for T-A[2] in A[3...N] and so on. Complexity. Sort=nlogn, find=n times logn. Total nlogn

As periaganesh told, hashing is the optimal approach to solve this problem

public class MapTarget {
	public static void main(String...v){
		
		int[] arr={2,6,8,4,5,1,7};
		int target =15;
		Map<Integer,Integer> map = new HashMap<Integer, Integer>();
		for (int i = 0; i < arr.length; i++) {
			 map.put(arr[i], arr[i]);
			}
		
		for (int i = 0; i < arr.length; i++) {
			int k= (int) map.get(arr[i]);
			 if(map.containsKey(target-k))
				 System.out.println(arr[i]);
			}
				
	}

}