TwoSum：两数相加得0

在一个不重复的数组中，统计有多少组两个元素相加得0。

这里使用三种方式实现，并统计他们各自花费的时间：

import java.util.Arrays;
import java.util.HashMap;
import java.util.Random;

public class TwoSum {
	private static int N = 100000;
	private static int[] a = new int[N];
	private static Random random = new Random();
	private static HashMap<Integer, Boolean> m = new HashMap<Integer, Boolean>();
	
	private int binarySearch(int[] a, int num) {
		int low = 0, mid = 0, high = a.length - 1;
		while (low <= high) {
			mid = low + (high - low) / 2;
			if (a[mid] > num) {
				high = mid - 1;
			} else if (a[mid] < num) {
				low = mid + 1;
			} else {
				return mid;
			}
		}
		
		return -1;
	}
	
	public int solution1() {
		int count = 0;
		for (int i = 0; i < N; i++) {
			for (int j = i + 1; j < N; j++) {
				if (a[i] + a[j] == 0) {
					count++;
				}
			}
		}
		return count;
	}
	
	public int solution2() {
		int count = 0;
		Arrays.sort(a);
		for (int i = 0; i < N; i++) {
			if (binarySearch(a, -a[i]) > i) {
				count++;
			}
		}
		return count;
	}
	
	public int solution3() {
		int count = 0;
		for (int i = 0; i < N; i++) {
			if (m.containsKey(-a[i])) {
				count++;
			}
		}
		return count / 2;
	}
	
	public static int uniform(int N) {
        if (N <= 0) throw new IllegalArgumentException("Parameter N must be positive");
        return random.nextInt(N);
    }
	
	public int uniform(int a, int b) {
        if (b <= a) throw new IllegalArgumentException("Invalid range");
        if ((long) b - a >= Integer.MAX_VALUE) throw new IllegalArgumentException("Invalid range");
        return a + uniform(b - a);
    }
	
	public static void main(String[] args) {
		TwoSum ts = new TwoSum();
		int count = 0;
		int rand = 0;
		int i = 0;
		boolean flag = true;
		
		while (i < a.length) {
			rand = ts.uniform(-10000000, 10000000);
			flag = true;
			for (int j = 0; j < a.length; j++) {
				if (a[j] == rand) {
					flag = false;
					break;
				}
			}
			if (flag) {
				a[i] = rand;			
				i++;
				//System.out.println(rand + " " + flag);
			}
		}
		
		for (int j = 0; j < N; j++) {
			m.put(a[j], true);
		}
		
		Stopwatch timer1 = new Stopwatch();
		count = ts.solution1();
		double time = timer1.elapsedTime();
		System.out.println("count1: " + count + " cost1: " + time);
		
		count = 0;
		time = 0;
		Stopwatch timer2 = new Stopwatch();
		count = ts.solution2();
		time = timer2.elapsedTime();
		System.out.println("count2: " + count + " cost2: " + time);
		
		count = 0;
		time = 0;
		Stopwatch timer3 = new Stopwatch();
		count = ts.solution3();
		time = timer3.elapsedTime();
		System.out.println("count3: " + count + " cost3: " + time);
	}
}

solution1:直接使用一个两层for循环，所以最终的时间复杂度为O(N^2)；

solution2:先将数组排序，然后通过二分查找来搜索数组中每个元素的相反数，此时的时间复杂度为O(N*log(N))；

solution3:和方法一类似，只不过是通过哈希表中查找元素的复杂度为O(1)来优化搜索时间，此时时间复杂度为O(N)；

当N=1000时

count1: 0 cost1: 0.004
count2: 0 cost2: 0.002
count3: 0 cost3: 0.001

当N=10000时

count1: 5 cost1: 0.026
count2: 5 cost2: 0.009
count3: 5 cost3: 0.005

当N=100000时

count1: 238 cost1: 2.296
count2: 238 cost2: 0.077
count3: 238 cost3: 0.012

这里因为产生不重复的随机数使用的是最简单的两层循环，所以当数组的length太大时，比如1000000时，在产生随机数的过程中会消耗很长时间，这一部分可以使用其他更优的方法实现。