给你一个数组，找出这个数组中是否有两个数的和为某个指定的值

gistfile1.java

// 给你一个数组，找出这个数组中是否有两个数的和为某个指定的值
// int array[] = {1, 4, 12, -1, 6, 4}, 
//     sum = 10, return true;
//     sum = 100, return false;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map.Entry;

public final class ArraySum
{
	
	// sort and binary search: n*lg(n)
	public static boolean hasSumAs_binarysearch(int[] array, int sum)
	{
		if(array.length <= 1) return false;

		Arrays.sort(array);
		
		for(int i = 0; i < array.length; ++i)
		{
			int element = array[i];
			int complement = sum - element;
			
			int index = Arrays.binarySearch(array, complement);
			if(index >= 0 && index != i)
				return true;
		}
		
		return false;
	}
	
	
	// bit array and count sort: o(n)
	// only allowed for non-negative values
	public static boolean hasSumAs_bitarray(int[] array, int sum)
	{
		if(array.length <= 1) return false;
		if(sum < 0) return false; // can use exception to report input error
		
		// get the max value
		int max = array[0];
		for(int element : array)
		{
			if(element < 0) return false; // can use exception to report input error
			
			if(element > max)
				max = element;
		}
		max = array.length > max ? array.length : max;
		
		// counter the bit array
		int[] counter = new int[max+1];
		for(int element : array)
		{
			counter[element] = counter[element] + 1;
		}
		
		// check sum
		for(int i = 0; i < counter.length; ++i)
		{
			if(counter[i] > 0)
			{
				int complement = sum - i;
				if(complement == i)
				{
					if(counter[i] >= 2)
						return true;
				}
				else
				{
					if(counter[complement] > 0) 
						return true;
				}
			}
		}
		
		return true;
	}
	
	// hash table: average o(n)
	public static boolean hasSumAs_hash(int[] array, int sum)
	{
		if(array.length <= 1) return false;
		
		HashMap<Integer, Integer> hash = new HashMap<Integer, Integer>();
		for(int element : array)
		{
			if(hash.containsKey(element))
			{
				hash.put(element, hash.get(element)+1);
			}
			else
			{
				hash.put(element, 1);
			}
		}
		
		for(Entry<Integer, Integer> entry : hash.entrySet())
		{
			Integer complement = sum - entry.getKey();
			// Bug1: don't use == for Integer to compare values.
			if(complement.equals(entry.getKey())) 
			{
				if(hash.get(complement) >= 2)
					return true;
			}
			else
			{
				if(hash.containsKey(complement))
					return true;
			}
		}		
		
		return false;
	}
	
	public static boolean hasSumAs(int[] array, int sum)
	{
		//return hasSumAs_hash(array, sum);
		return hasSumAs_binarysearch(array, sum);
	}

}