今日有朋友问我一些python入门的免费教程。不知怎的就想到了刷题，就想看看是怎么个流程， 然后就搜索了下，网上推荐的网站：https://leetcode-cn.com/
为了看这个检查的流程，就找了个最简单的，语言使用最近经常使用的javascript.刚开始的时候， 无论如何执行，执行结果都没有。后来发现是浏览器的广告拦截插件的原因。于是关闭后刷新总算 执行正常了。
因为两数之合很简单，就随便写了个常规的流程，提交后发现可以看到执行效率的排名，内存占用的排名。 比如下面的常规的流程：
//方法1:
//执行用时: 100 ms
//内存消耗: 41.3 MB
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function(nums, target) {
for(let i =0; i < nums.length; i++) {
for(let j=i+1; j < nums.length; j++) {
if(nums[i]+nums[j] === target) {
return [i,j];
}
}
}
return [-1,-1];
};
我的提交显示 执行效率超过46%（100ms)，内存超过44%(41.3 MB)
这激发了我的兴趣，就想着如何优化或者负优化吧。于是就有了下面更多的提交：
//方法2:
//执行用时: 520 ms
//内存消耗: 42.6 MB
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function(nums, target) {
for(let i =0; i < nums.length; i++) {
let test = target - nums[i];
let index = nums.findIndex((e, j)=> j != i && e == test );
if(index >= 0) {
return [i, index];
}
}
return [-1,-1];
};
上面这个方法似乎效率超越了2%， 我不知道哪个比这个还要慢了。
//方法3:
//执行用时: 72 ms
//内存消耗: 41.7 MB
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function(nums, target) {
let obj = {};
for(let i =0; i < nums.length; i++) {
if(obj[nums[i]] != undefined) {
return [obj[nums[i]], i];
} else {
obj[target-nums[i]] = i;
}
}
return [-1,-1];
};
上面的方法使用了json的格式，利用判断key是否存在，但json格式的key只能是字符串，利用题目中的 索引都是数字的特性，简单优化了下类型：
//方法4:
//执行用时: 64 ms
//内存消耗: 41.6 MB
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function(nums, target) {
let obj = [];
for(let i =0; i < nums.length; i++) {
if(obj[nums[i]] != undefined) {
return [obj[nums[i]], i];
} else {
obj[target-nums[i]] = i;
}
}
return [-1,-1];
};
数组的方式比object的方式快一些
//方法5:
//执行用时: 60 ms
//内存消耗: 41.5 MB
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function(nums, target) {
let obj = [];
for(let i =0, j=nums.length-1; i <= j; i++, j--) {
if(obj[nums[i]] != undefined) {
return [i, obj[nums[i]]];
} else {
obj[target-nums[i]] = i;
if(obj[nums[j]] != undefined) return [obj[nums[j]],j];
else
obj[target-nums[j]] = j;
}
}
return [-1,-1];
};
上面的方式还是使用数组的方式，只是将循环减半了。因此复杂度也少了些了。
//方法6
//执行用时: 60 ms
//内存消耗: 41.4 MB
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function(nums, target) {
let obj = new Map();
for(let i =0, j=nums.length-1; i <= j; i++, j--) {
if(obj.has(nums[i])) {
return [i, obj.get(nums[i])];
} else {
obj.set(target-nums[i], i);
if(obj.has(nums[j])) return [obj.get(nums[j]),j];
else
obj.set(target-nums[j], j);
}
}
};
使用map，不影响效率的同时，降低了内存消耗
//方法7
//执行用时: 64 ms
//内存消耗: 41.4 MB
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function(nums, target) {
let obj = new Map();
let i = 0;
let j = nums.length-1;
while(i<=j) {
let left = nums.shift();
let right = nums.pop();
if(obj.has(left)) {
return [i, obj.get(left)];
}
obj.set(target-left, i);
if(obj.has(right)) {
return [obj.get(right), j];
}
obj.set(target-right, j);
++i;
--j;
}
};
方法7与方法6基本一样，只是将for循环使用while循环来代替了，并且，旨在为了降低内存使用的shift, pop 操作，从测试结果而言，并没有效果。这应该和javascript的内存分配机制有关系，毕竟变量nums还在不断的使用中。
//方法8
//执行用时: 64 ms
//内存消耗: 41.6 MB
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function(nums, target) {
let obj = [];
let i = 0;
let j = nums.length-1;
while(i<=j) {
let left = nums.shift();
let right = nums.pop();
if(obj[left] != undefined) {
return [i, obj[left]];
}
obj[target-left] = i;
if(obj[right] != undefined) {
return [obj[right], j];
}
obj[target-right] = j;
++i;
--j;
}
};
方法8与方法7一样，只是将map修改成了数组。执行效率一样，但内存占用多了些。
//方法9:
//执行用时: 72 ms
//内存消耗: 41.5 MB
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function(nums, target) {
let obj = new Map();
let i = 0;
let j = nums.length-1;
while(i<=j) {
let left = nums[i];
let right = nums[j];
if(obj.has(left)) {
return [i, obj.get(left)];
}
obj.set(target-left, i);
if(obj.has(right)) {
return [obj.get(right), j];
}
obj.set(target-right, j);
++i;
--j;
}
};
方法9与方法7一样，只是将数据的提取使用数组的方式，而非shift,pop的方式， 即使这一简单改变，也导致 测试执行效率降低了些。
//方法10
//执行用时: 52 ms
//内存消耗: 41.7 MB
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function(nums, target) {
let obj = {};
let i = 0;
let j = nums.length-1;
while(i<=j) {
let left = nums.shift();
let right = nums.pop();
if(obj[left] != undefined) {
return [i, obj[left]];
}
obj[target-left]= i;
if(obj[right] != undefined) {
return [obj[right], j];
}
obj[target-right]= j;
++i;
--j;
}
};
方式10和方法9一样，只是使用了object和数组的shift,pop的方法，
除了负优化的方法2之外，总体而言，减少循环可以优化效率。使用object和map的方式会比较节约些内存。 受到数据样本情况，上面的测试结果也不是非常准确的，比如，如果数据样本大都集中在前面几个就有 答案的话，方法1可能比较快的，反之，方法1则是比较慢的；如果数据样本的答案集中在两侧的话，循环减半 的方式则相对比较快，（对于前一种情况，循环减半效果也比较好）。即使是同一个算法，每次提交 执行用时也不相同，不如方法10，我这边在测试的时候，最快在52ms, 而排在前面的小于40ms的，我将 算法提交上去后，却在64ms，方法7有时候也会执行用时也会在56ms左右。
其实无论何种方式，何种优化，关键是从何种角度去思考问题，解决问题。