Given an array find any pair that sums up into a number

This problem is quite largely discussed and is very famous for its various ways to attack. This can be constrained in time and in space. The most primitive way of attacking this problem would yield an solution that runs in O(n²) time.
Let me define the problem clearly. Given an array of size n and a number X, you are supposed to find a pair of numbers that sums to X. Only one pair would be enough.
Lets see how we can find the solution for this in O(n) using a HashSet. Yes, HashSet is a costly data structure to use, but lets consider this primitive just due to the linear order it provides.

	package dsa.arrays;
	import java.util.HashSet;
	import java.util.Set;
	public class FindSumHashSet {
	public static void main(String a[]){
	FindSumHashSet sumFinder = new FindSumHashSet();
	sumFinder.begin();
	}
	public void begin(){
	int[] sampleArray = getRandomArray(20);
	int randomSum = sampleArray[15] + sampleArray[10];
	System.out.print("ARRAY : ");
	for(int i:sampleArray){
	System.out.print(i+" ");
	}
	System.out.println();
	findPair(sampleArray,randomSum);
	}
	public void findPair(int[] sampleArray, int randomSum) {
	Set<Integer> sampleArraySet = new HashSet<Integer>();
	for(int i=0;i<sampleArray.length;i++){
	sampleArraySet.add(sampleArray[i]);
	int valueToFind = randomSum - sampleArray[i];
	if(sampleArraySet.contains(valueToFind)){
	System.out.println("SUM : "+randomSum);
	System.out.println("PAIR : "+valueToFind+","+sampleArray[i]);
	break;
	}
	}
	}
	private int[] getRandomArray(int size) {
	int[] randomArray = new int[size];
	for(int i=0;i<size;i++){
	randomArray[i] = (int)(Math.random()*10);
	}
	return randomArray;
	}
	}
	//SAMPLE OUTPUTS
	//ARRAY : 7 3 6 4 3 4 7 7 5 1 4 6 2 4 1 7 5 8 9 7
	//SUM : 11
	//PAIR : 7,4
	//ARRAY : 0 2 9 6 0 7 6 5 1 7 9 0 7 1 2 4 4 3 9 0
	//SUM : 13
	//PAIR : 6,7

view raw FindSumHashSet.java hosted with ❤ by GitHub

We shall improvise on this problem in space domain using fancy sorts and those we shall see in the coming posts.

Cheers,
Bragaadeesh