Amazon-Two Sum (Easy)

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

Java Solution:

public int[] twoSum(int[] nums,int target){
    if(nums==null) return null;
    int[] res=new int[2];
    Map<Integer,Integer> map=new HashMap<>();    
    for(int i=0;i<nums.length;i++){
        if(map.containsKey(target-nums[i])){
            res[1]=i;
            res[0]=map.get(target-nums[i]);
            return res;
        }
        map.put(nums[i],i);
    }
    return null;
}

时间复杂度：O(n)
空间复杂度：O(n)

暴力双循环也可以实现，外层从数组0开始，内层从外层后一个位置开始，判断target-nums[j]是否等于nums[i]。时间复杂度O(n^2)，空间复杂度O(1)。

用哈希表有两种实现方式。
第一种是遍历两次数组，第一次存放数组与位置的键值对，第二次遍历检测target-nums[i]是否在哈希表中，这里需要特别注意，判断是否存在时要加上判断存在的值是不是遍历当前数组的位置，如果是的话，代表它在和自己相加！这样是肯定错误的。
第二种是只遍历一次，边遍历，边检测，这样会消除可能会和自己相加的情况。循环中先判断是否存在target-nums[i]，存在的话说明之前遍历的值存在和当前值相加为target，这样就直接返回res就好了。

测试用例：

[3,2,4]
6
return [1,2]
[2,7,11,15]
9
return [0,1]
null
0
return null
[]
0
return null
[0,1,2147483647]
2147483647
return [0,2]
[-2147483648,1,2147483647]]
-2147483648
return null

题目中规定了每一组输入有唯一解，且同一个数字不会用到两次，所以在遍历中一定会返回，但是保险起见，实际中条件都可能会变化，所以测试用例想了一些可能会出现的情况。总之无论哪种方法最好还是判断一下nums是否为null，不然调用nums.length会出现空指针的异常。Solution的代码还是可以跑通题目的要求。