算法：两数之和

给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。
你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

代码如下，类似冒泡排序的写法，i从0到num.length-1，j从i+1到nums.length：

class Solution {
    public int[] twoSum(int[] nums, int target) {
        for(int i=0;i<nums.length-1;i++){
            for(int j=i+1;j<nums.length;j++){
                if(nums[i]+nums[j]==target){
                    return new int[]{i,j};
                }
            }
        }
        return null;
    }
}

但是上面这种写法存在几个问题，首先没有异常处理，然后效率也不行，下面的这个算法要好很多：

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int [] res = new int[2];
        if(numbers==null||numbers.length<2)
            return res;
        HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
        for(int i = 0; i < numbers.length; i++){
            if(!map.containsKey(target-numbers[i])){
                map.put(numbers[i],i);
            }else{
                res[0]= map.get(target-numbers[i]);
                res[1]= i;
                break;
            }
        }
        return res;
    }
}

异常处理就不细说了，从时间复杂度上来说，算法1是T(n^2)，空间复杂度O(1)；算法2是T(n)，空间复杂度O(n)；
提升的关键，就在于使用了一个map，用array元素的值作为key，array的下表作为value，利用哈利表的快速查找优势，用空间换取了时间。

用空间换时间，以前算法课经常到，不理解，但是我们后来常用的很多手段，比如memcached、redis等缓存，都属于是空间换取时间。

根据leetcode的测试，算法1平均需要31ms，算法2仅需要8ms，一个普通的加减法，时间就缩短到原来的1/4，真的是很恐怖的提升，算法的力量。

需要注意的是，算法2也不是绝对优势，因为空间复杂度相对提升，这个例子里面，我们不太能感受到空间复杂度提升带来的副作用，但是如果我们要计算的数据很大，比如大到100GB，而你可支配的内存只有64GB，那算法2就不行了。那算法1呢，可能内存是不需要太多，但是需要1个月来计算，那也不行。最好的办法可能就是“折中”，找到一个最适合自己的那个“度”，不浪费空间，又节省时间。

突然想到一句话叫“万法皆有度”，这个万法应该也包括算法吧，哈哈。