先从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].
第一次提交(已经很久以前了)
public class Solution {
public int[] twoSum(int[] nums, int target) {
for(int i = 0; i<nums.length-1; i++ ){
int num1 = nums[i];
int num2 = target-num1;
for(int j = i+1; j<nums.length;j++){
if(num2==nums[j]){
return new int[]{i,j};
}
}
}
return new int[]{1,1};
}
}
用了2个for循环，穷举了所有的可能，直到找到正确的结果。
看下runtime：
可以看出效率是比较低的。
首先遍历数组，时间复杂度是Θ(n)，每个循环里面又需要遍历一部分的数字，时间复杂度是Θ(n)，总的时间复杂度是Θ(n2)。
那么如何提升呢？首先数组是肯定要遍历一次的，那么只能在每一步的操作上面思考了。
for(int i = 0; i < nums. length; i++)当循环到 nums[i] 的时候，需要快速的确定是否存在与其和为target的数，如何做到使这一步的复杂度小于Θ(n)呢？看了下提示，那就是使用HashMap。
因为HashMap查找的时间复杂度是Θ(1)，所以整体的时间复杂度可以降到Θ(n)！
第二次提交
public class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> exist = new HashMap();// map<数字，序号>
for(int i = 0 ; i < nums.length; i++){
if(exist.keySet().contains(nums[i])){
return new int[]{exist.get(nums[i]), i};
}
exist.put(target - nums[i], i);
}
return new int[]{0,0};
}
}
可以看到，runtime明显提升了一大截。
最后看看最快的是怎么做的，只用了3ms：
public class Solution {
public int[] twoSum(int[] nums, int target) {
short[] map = new short[20050];//新建一个map数组做映射
int size = 50;
for (int i = 0; i < nums.length; i++) {
map[nums[i] + size] = (short) (i + 1);
int diff = target - nums[i + 1] + size;
if (diff < 0) continue;
short d = map[diff];
if (d > 0)
return new int[]{d - 1, i + 1};
}
return null;
}
}
看起来一脸懵逼，循环里面的语句一句句分析一下。
map[nums[i] + size] = (short) (i + 1);
每遍历一个数组元素，把其序号+1保存在map[nums[i] + size] 中。（为什么保存i + 1而不保存i，是因为如果i == 0的话就不能分辨出是默认值还是有保存过了）相当于建立了 nums[i] + size -> i + 1 [1] 的映射关系（事实上，nums[i] + size很可能是负数，理论上不应该这么写）。
int diff = target - nums[i + 1] + size;
这个diff是什么含义？target - nums[i + 1] 好理解，其和数组第i + 1项的和是target，满足题目要求。假设这个数存在于nums数组中，且他的序号为k，即：
nums[k] == target - nums[i + 1]，
那么：
diff == nums[k] + size，
眼熟啊！从[1]式中可以看出，在map数组中：
nums[k] + size -> k + 1，
即是在map数组中的对应关系是
diff -> k + 1
short d = map[diff];
if (d > 0)
return new int[]{d - 1, i + 1};
这样分析过来，这句话就好理解了：如果对于nums[i + 1]来说，和其和为target的数nums[k]已经遍历过并保存在了map中，那么map中一定会有：
diff -> k + 1
这个对应关系，即 d == map[diff] == k + 1。我们知道java中short默认值为0，而 k + 1必然是大于0的，所以如果 d > 0，说明：
nums[i + 1] + nums[k] == target，
满足题目条件，因为d == k + 1，所以返回：
return new int[]{d - 1, i + 1};
逻辑并不是很难，本质上和hashmap有异曲同工之妙，但是有个magic numberint size = 50;这个根据数据集来的数，看来是针对测试集精心准备的。
