1.Two Sum
这是leetCode第1题,难度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].
下面是我的代码：
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function(nums, target) {
var l = nums.length;
for(var i=0;i<l;i++){
for(var j=i+1;j<l;j++){
if(nums[i]+nums[j]===target){
result = [i,j];
return result;
}
}
}
};
简单测试一下：
twoSum([3,2,4,5],7) // result: [0,2]
twoSum([3,2,4,5,8,11,28,16,13,8,7,21],44) //result:[6,7]
OK测试通过了，我很兴奋，这题目真简单。
可是，我的代码执行效率很低。因为我的做法很暴力，循环遍历每个数字，然后寻找是否有一个数字和当前位置的数字的和，等于target。
这种做法的时间复杂度为：O(n^2);
高手们的做法：
其实我们可以一次性完成，不需要在循环中嵌套循环。
高手们的做法：迭代数组并将元素作为对象的属性，索引作为该属性的值。每次都检查一下，对象中是否存在target与当前元素的差值。如果存在，我们已经找到一个解决方案并立即返回。
var twoSum = function(nums, target) {
var map = {};
for(var i = 0; i < nums.length; i++) {
var check = nums[i];
var search = target - check;
if(map[search] === undefined) {
map[check] = i;
} else {
return [map[search], i];
}
}
};
下面，测试一下两种算法花费的时间大小：
按照下面的代码，创建一个模块Array.js，导出一个长度为10000000的整型数组：
node product.js
product.js文件的代码如下
var fs = require("fs");
var nums =[];
var boundary = 10000000;
for(var i=0;i<boundary;i++){
nums.push(Math.floor(Math.random()*boundary));
}
//转成字符串
var str = "var array=["+nums+"];module.exports=array;";
//写入Array.js文件，生成了js代码
fs.writeFile('Array.js', str, function(err) {
if (err) {
return console.error(err);
}
console.log("数据写入成功！");
});
使用下面的代码测试算法：
var nums=require('./Array.js');
var start = new Date().getTime();
console.log("result : "+twoSum(nums,877656));
var end = new Date().getTime();
console.log("time: "+(end-start));
第一种算法的结果：
result : 4,5008617
time: 124
第二种算法的结果：
result : 977,24257
time: 22
因为算法不同，可能找到结果不同。
但是，第二种算法的时间，明显更快。
再看下另一个测试结果
var nums=require('./Array.js');
var start = new Date().getTime();
console.log("result : "+twoSum(nums,45678));
var end = new Date().getTime();
console.log("time: "+(end-start));
第一种算法的结果：
result : 154,5721777
time: 3893
第二种算法的结果：
result : 42904,74847
time: 72
结果还是第二种算法更快。
