一个很常见的问题，找出一个数组中和为给定值的两个数的下标。为了简单一般会注明解只有一个之类的。
最容易想到的方法是循环遍历，这里就不说了。
在JS中比较优雅的方式是利用JS的对象作为hash的方式：
var twoSum = function(nums, target) {
var hash = {};
var i;
for (var i = 0; i < nums.length; i++ ) {
if (typeof hash[nums[i]] !== "undefined") {
return [i, hash[nums[i]]];
}
hash[target - nums[i]] = i;
}
};
这里面还可以做一些小的优化，比如把length拿出来，重复使用的 nums[i] 也抽取出来，遍历的顺序反过来等，最后大概弄成这个样子：
var twoSum2 = function(nums, target) {
var hash = {};
var i;
var tmp;
for (i = nums.length; i--; ) {
tmp = nums[i];
if (typeof hash[tmp] !== "undefined") {
return [i, hash[tmp]];
}
hash[target - tmp] = i;
}
};
不过这些小的优化基本上不影响大局，在leetcode上测试了好几遍，排名总在75%到85%之间浮动。居然连90%都没达到，我对你很失望
让我再想想……
哦对了我记得前几天看到过一个优化循环的方法叫做Duff Device来着，不如试试？
链接在这里 https://en.wikipedia.org/wiki/Duff%27s_device。（怎么插入链接来着？）
这东西我的大概理解就是就是把for循环稍微展开一下，本来循环80次的行为，改写成执行10次循环，每次循环里执行8次。这样可以省下一点调用for循环的开销。不过这个前提是for循环里的执行代码比较简单。如果耗时主要在每个循环里的话，这招就不太管用了听说。
于是我照着介绍的例子，把上面的代码改写了一下：
var twoSum1 = function(nums, target) {
var hash = {};
var i = 0;
var startIndex = nums.length % 8;
var iterations = nums.length / 8;
do {
switch(startIndex) {
case 0: if(typeof hash[nums[i]] !== "undefined") {return [i, hash[nums[i]]]} hash[target - nums[i]] = i; i++;
case 7: if(typeof hash[nums[i]] !== "undefined") {return [i, hash[nums[i]]]} hash[target - nums[i]] = i; i++;
case 6: if(typeof hash[nums[i]] !== "undefined") {return [i, hash[nums[i]]]} hash[target - nums[i]] = i; i++;
case 5: if(typeof hash[nums[i]] !== "undefined") {return [i, hash[nums[i]]]} hash[target - nums[i]] = i; i++;
case 4: if(typeof hash[nums[i]] !== "undefined") {return [i, hash[nums[i]]]} hash[target - nums[i]] = i; i++;
case 3: if(typeof hash[nums[i]] !== "undefined") {return [i, hash[nums[i]]]} hash[target - nums[i]] = i; i++;
case 2: if(typeof hash[nums[i]] !== "undefined") {return [i, hash[nums[i]]]} hash[target - nums[i]] = i; i++;
case 1: if(typeof hash[nums[i]] !== "undefined") {return [i, hash[nums[i]]]} hash[target - nums[i]] = i; i++;
}
} while (--iterations);
};
嗯，看上去很厉害的样子。接下来在浏览器里测试一下：
先构造一个长度为1000的数组，来来来：
呃……好像没什么差别。把数据加大一点，到100000吧：
卧槽牛逼啊！赶紧把这个放leetCode上试试！
……
……
……
然而在leetCode上试了之后，虽然通过了，发现和之前的执行效率并没有多大差别……依然没有到90%
一定是leetCode上的单测数据太小了！于是自个儿在leetCode上的那个小输入框里粘贴了一个十几万长度的数据，跑了一遍，发现仍然没有什么卵用。
所以大概是我的测试方法有问题？数据翻了100倍时间居然并没有增加多少，好奇怪。
好吧，这个方法就暂时搁着。再想想其它歪主意。
用js自带的forEach做循环试试吧，说不定会比手写的要快点。于是有了下列代码：
var twoSum = function (nums, target) {
var hash = {};
var result = [];
nums.forEach(function (v, i) {
if (typeof hash[v] !== "undefined") {
result[0] = i;
result[1] = hash[v];
}
hash[target - v] = i;
});
return result;
}
不过这有个问题是，forEach循环没法正常地退出，所以无论怎样都要遍历一下整个数组，不能像前面那样找到正确的就退出了，感觉太好。
所以只能让它不正常地退出了：
var twoSum = function (nums, target) {
var hash = {};
var result = [];
try {
nums.forEach(function (v, i) {
if (typeof hash[v] !== "undefined") {
result[0] = i;
result[1] = hash[v];
throw "err";
}
hash[target - v] = i;
});
} catch (err) {
return result;
}
}
好的就这样，跑一下试试：
噢好吧，好歹过了90%……
想到更快的方法再更………………