题目：
给定一个整数数组和一个目标值，找出数组中“和”为目标值的两个数。
你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
看到这个问题的时候，优先想到了一开始学习Java时老师教的方法，没错，就是暴力解决法，使用循环嵌套，判断筛选出符合条件的值，如下：
class Solution {
public int[] twoSum(int[] nums, int target) {
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
if (nums[j] == target - nums[i]) {
return new int[] { i, j };
}
}
}
throw new IllegalArgumentException("没有想要的结果");
}
}
比较好理解，拿出数组中的某个数，和其他的数求和，看看是不是和目标值相同。（为了避免重复求和，在子循环中，初始值用的是父循环的下一个值，因为并不是所有值都需要从第一个开始求和判断，比如说第三个值，它只需要和第四个以及第四个之后的求和判断就可以了，因为它之前的值，早在第一个、第二个值循环求和判断的时候和它相加过了。并且题目要求元素不能重复利用，所以这里用到“i+1”。）
对是对了，但提交代码后我懵圈了。。。运行时间：56ms，超过13.11%的人。纳尼？还有这个统计。。我岂能忍得了这个排名！
开始改良代码，首先我觉得主要是我用到了两个循环的问题，那么我就舍弃一个循环。可是怎么做呢？我想到一个方法，首先我将nums数组转换成一个List，然后在一个循环中，看目标值和nums里值的差是否存在于List里，如果存在，那就找到了这两个值了。
但是问题来了，基本类型的数组没法直接转换成List，这就有点尴尬了，不过我又有了一个点子。
那就是逆向思维，我先new一个List，然后在循环求差判断的时候，如果符合条件，我就return结果，如果不符合条件，我就将当前的nums里值放到List里，然后下次循环，会将求差结果和List里的值比较，之前的方法是不用和当前值之前的值进行比较，现在是每个值不用和它之后的值进行比较，因为后面的值会和它之前的值(之前add到List里的所有的值)比较，同样起到了避免重复判断的作用。
这里我说的太绕，换句话说：在进行循环并将元素插入到List中的同时，我们还会回过头来检查List中是否已经存在当前元素所对应的目标元素(求差结果)。如果它存在，那我们已经找到了对应解，并立即将其返回。代码如下：
class Solution {
public int[] twoSum(int[] nums, int target) {
List<Integer> numsList = new ArrayList<Integer>();
for(int i=0; i<nums.length; i++){
int j = numsList.indexOf(target - nums[i]);
if(j>-1 && j!=i){
return new int[]{j,i};
}
numsList.add(nums[i]);
}
throw new IllegalArgumentException("没有想要的结果");
}
}
啊？啊？啊♂~~~~为啥这么慢。。ArrayList查询比较速度应该很快啊。。。
额，忽略一件事，因为ArrayList底层是数组实现的，增删操作会带来元素的移动，增加数据会向后移动，所以极大影响效率。
既然这样，那就用同样的思想，换成HashMap好了，哈希表添加值的话是很快的，将nums里值作为HashMap的key，将下标作为value，这样就可以用containsKey方法找到符合条件的键值，和List的indexOf在这里有异曲同工之处。
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer,Integer> map = new HashMap<Integer,Integer>();
for(int i=0; i<nums.length; i++){
int key = target - nums[i];
if(map.containsKey(key)&&map.get(key)!=i){
return new int[]{map.get(key),i};
}
map.put(nums[i],i);
}
return new int[]{};//这样比异常更快，为了速度。。
}
}
果不其然，这个结果就让我很满意了。
很好奇大佬们究竟用了什么方法，能够更快，于是参考了大佬的代码。我哩个龟龟。。。二进制运算。。。在这里贴一下Top1的代码，用时 3ms，供大家观赏。
class Solution {
public int[] twoSum(int[] nums, int target) {
final int il = nums.length;
int il2 = (il >> 2) - 1;
int pot = 2;
while((il2 >>= 1) > 0) pot <<= 1;
final int bitMod = pot - 1;
final int[] bucket = new int[pot];
final int[] linked = new int[il];
final int firstVal = nums[0];
for (int i = 1; i < il; i++) {
int currNum = nums[i];
int complement = target - currNum;
if (complement == firstVal) {
return new int[] { 0, i };
}
int complementLLIndex = bucket[complement & bitMod];
while(complementLLIndex != 0) {
if(nums[complementLLIndex] == complement) {
//Found
return new int[] { complementLLIndex, i };
}
complementLLIndex = linked[complementLLIndex];
}
int currNumLLIndex = currNum & bitMod;
linked[i] = bucket[currNumLLIndex];
bucket[currNumLLIndex] = i;
}
return null;
}
}