CareerCup

Sort, maintain two pointers one at left end and one at right. Move them (standard solution). O(n log n).

A detailed explanation here:
tech-queries.blogspot.com/2010/12/ sum-of-2-nos-in-array-equal-to-given.html

A detailed explanation here:
tech-queries.blogspot.com/2010/12/sum-of-2-nos-in-array-equal-to-given.html

While creating the hash , we only pick the values which are less than x always , once the processing of array is done , we have the hash with <n elements ,for element(a) in hash , find the another element ST , x-a which is b.. this will be faster..

private List<Pair> findSum( final int[] arr , int sum ){
		
		final Map<Integer, Integer> elems = new HashMap<Integer, Integer>();
		
		// O(N)
		for( int value : arr ){
			
			Integer counter = elems.get(value);
			
			if( counter == null ){
				counter = Integer.valueOf(1);
			}
			else {
				counter += 1;
			}
			
			elems.put( value, counter );
		}
		
		final List<Pair> pairs = new ArrayList<Pair>(); 
		
		// O(N)
		for( int value : arr ){
			
			Integer curCounter = elems.get(value);
			elems.put( value, curCounter-1 );
			
			int neededValue = sum - value;
			
			Integer neededCounter = elems.get(neededValue);
			
			if( neededCounter != null && neededCounter > 0 ){
				pairs.add( new Pair(value, neededValue) );
				elems.put(neededValue, neededCounter-1);
			}
		}
		
		return pairs;	
	}

void printNumbersWithSum(const int arr[], const int size, const int sum) { 
    std::set<int> numbersRequired; 
    std::set<int> :: iterator iter ;

    for (int i = 0; i < size; i++) { 
        iter = numbersRequired.find(arr[i]); 
        if (iter != numbersRequired.end()) { 
            std::cout<<(sum - arr[i])<<" + "<<arr[i]<<"   = "<<sum<<std::endl; 
        }   
        else { 
            numbersRequired.insert(sum - arr[i]); 
        }   
    }   
}

// first we sort the array using O(nlogn) approach
// then use the following method...
// overall solution = nlogn + n = nlong

int arr[] = {-2,0,1,2,3,6,10,19,21,23,43};

int start=0, end = arr.length-1;
int x= 0;

while (start<end) {

if(arr[start]+arr[end]<x)
start++;
else if(arr[start]+arr[end]>x)
end--;
else if(arr[start]+arr[end]==x){
System.out.println("pair " + arr[start] + " " + arr[end]);
break;
}
}

sort the array first, and then check the sum form the two ends. Increment both ends towards center until all pairs are found.

Ask someone who knows it..... there should be someone right? c'mon, there shud be

private static void TwoNumbersSumIndex(int[] arr, int val)
{
Hashtable searchTbl = new Hashtable();
int lookFor = 0;
for(int i=0; i < arr.Length; i++)
{
searchTbl.Add(arr[i], i);
lookFor = val - arr[i];
if (searchTbl[lookFor] != null)
{
Console.WriteLine("Matching numbers - " + lookFor + " & " + arr[i]);
return;
}
}
}

Use a hash table,thatshould be linear
Or Hire 'N' people n solve in logN time

Sort and perform binary search for sum-a[i] for each element--O(nlogn)