Find pairs of integers in an array that sum to a value

Design an algorithm to find all pairs of integers within an array which sum to a specified value.

My initial thoughts:
For each element a in the array, we can find its complement s-a in the array and output this pair. To speed up the search, we can use binary search. Therefore we need to sort the array first, O(n\log n). Then for each element, we search for its complement, that’s another O(n\log n). Together it’s still O(n\log n).

My initial codes:

	public static boolean binarySeach(int[] array, int element) {
		int low = 0;
		int high = array.length;
		while (low <= high) {
			int mid = low + (high - low) / 2;
			if (element < array[mid])
				high = mid;
			else if (element > array[mid])
				low = mid + 1;
			else
				return true;
		}
		return false;
	}

	public static List<Pair<Integer>> findSum(int[] array, int sum) {
		Arrays.sort(array);
		List<Pair<Integer>> result = new LinkedList<Pair<Integer>>();
		Set<Integer> visited = new HashSet<Integer>();
		for (int i = 0; i < array.length; ++i) {
			int a = array[i];
			if (!visited.contains(a)) {
				visited.add(a);
				int b = sum - a;
				if (binarySeach(array, b)) {
					visited.add(b);
					result.add(new Pair<Integer>(a, b));
				}
			}
		}
		return result;
	}

Solution:

	public static void printPairSums(int[] array, int sum) {
		Arrays.sort(array);
		int first = 0;
		int last = array.length - 1;
		while (first < last) {
			int s = array[first] + array[last];
			if (s == sum) {
				System.out.println(array[first] + "" + array[last]);
				++first;
				--last;
			} else {
				if (s < sum)
					++first;
				else
					--last;
			}
		}
	}

Comments: the solution utilizes the state of sorted array and does a two-way search. Therefore after sorting, we only need one scan of the array. Altogether it ‘reduces’ the time complexity to O(n\log n + n).

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: