题目:传送门
类别:数组
难度:简单
容易想到的解法
n^2
次循环。第一级循环取数,算得目标数字,第二级看目标数字在不在数组中。最多优化下第二级循环,已经遍历过的就不管了。
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function(nums, target) {
for (let i = 0, len = nums.length; i < len; i += 1) {
const item = nums[i];
const that = target - item;
const thatIndex = findIndex(nums, i + 1, that);
if (thatIndex !== -1) {
return [i, thatIndex];
}
}
};
function findIndex(nums, from, target) {
for (let i = from, len = nums.length; i < len; i += 1) {
if (target === nums[i]) {
return i;
}
}
return -1;
}
最优解
空间换时间。需要一个哈希表。第一级循环取数,算得目标数字,去哈希表看有没有它,有的话结束程序,没有的话存入当前数,key
为当前数,value
为当前 index
。
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function(nums, target) {
const map = {};
for (let i = 0, len = nums.length; i < len; i += 1) {
const item = nums[i];
const that = target - item;
const thatIndex = map[that];
if (thatIndex === undefined) {
map[item] = i;
} else {
return [i, thatIndex];
}
}
};
实际测试发现,两个方法内存开销差不多,后者时间开销是前者的一半。
发表回复