给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
我的解答：
class Solution {
public int[] twoSum(int[] nums, int target) {
int length = nums.length;
//i j 首位两个数字
for (int i = 0 ,j = length -1;i < j ;i++,j--){
if (nums[i] + nums[j] == target) {
return new int[]{i,j};
}
// k 是i 后面的一位
for (int k = i +1; k < j; k++){
// 如果满足条件 返回 否则k 移动
if (nums[i] + nums[k] == target){
return new int[]{i,k};
}else if (nums[j] + nums[k] == target){
return new int[]{k,j};
}
}
// 全都不满足条件 ij 移动
}
return null;
}
}
网上最快的解答：
class Solution {
int size = 2048;
int[] map = new int[size];
int length = 2047;
int index;
public int[] twoSum(int[] nums, int target) {
for (int i = 0; i < nums.length; i++) {
index = nums[i]&length; //
if (map[index] != 0) {
return new int[] { map[index] - 1, i };
} else {
map[(target - index)&length ] = i + 1;
}
}
throw new IllegalArgumentException("No two sum solution");
}
}
这个算法我看了大概三天（因为我还要工作，没有大块的时间去研究），花了图，转换成二进制，才终于明白作者的大概意思。
当然，同时也看出了这个算法的漏洞。
比如：
twoSum(new int[]{2047,0, 800001, 800000, 7,2,2048}, 4095);
返回的结果是[0,1]，第0个元素和第一个元素，相加显然不等于4095.
作者大概的执行思路是：
1100 0011 0101 0000 0000 800000 num[i]
111 1111 1111 2047 length
101 0000 0000 1280 index
1 1000 0110 1010 0000 0000 target 1600000
101 0000 0000 index
1 1000 0110 0101 0000 0000 target -index
111 1111 1111 2047 length
101 0000 0000
补充：2047 二进制是11111111111 （11个1）
首先取出一个数，然后让这个数num[i]&2047 = a
之后取判断map[a]是不是0（存不存在），如果不是0（存在的话）就直接返回这个数的索引，和存在的map 里面的索引。
如果不存在，就让target - num[i] ,然后&2047（11个1）。
漏洞分析：
在作者的思想里，11位就可以确定一个数字，同时也认为，target 减去这个数之后的11 也可以确定是一个数。其实是错误的。23位到11这区间的数据，作者没有关心。这算法从这里看就是有漏洞的。我们就从23位到11位之间做文章，就可以得到这个算法的漏洞。
比如在做着的算法里，0 和2048（100000000000） 是一个数字 因为，最后11位都是0. 根据这个漏洞去反推作者的算法。
目标数 1111 1111 1111 （4095）
我找的数组的第一个数是 111 1111 1111 （2047）
1111 1111 1111 （4095） - 111 1111 1111 （2047） = 100000000000
然后和11111111111 做& 运算之后的数字是0
这时候如果第二个数字是0，就直接返回了0 和 2048，根本不是target 4095
比如
twoSum(new int[]{2047,0, 800001, 800000, 7,2,2048}, 4095);
这个结果应该是0，6， 但是按照网上最快的，返回是0，1。
是因为：
首先，第一个数2047是
111111111111（11个1） & 2047 等于 2047（11个1）
然后targe（4095 ） - 2047 相当于 111111111111（12个） - 11111111111(11个1) = 100000000000 (应该是2048)
然后把这个数100000000000 (2048) & 2047 = 0
然后把map[0] = 1
到第二个数的时候，0 & 2047 = 0 ，发现这个数存在，就取出来返回。结果两个数之后是2047 ，根本不是我想要的4095