Open AmelloAster opened 5 years ago
/**
var twoSum = function(nums, target) { let indexAry = []; for (let i = 0;i < nums.length; i++) { let dataI = nums[i]; if (i === nums.length - 1) { continue; } for (let j = i+1; j < nums.length; j++) { let dataJ = nums[j]; if (dataI + dataJ === target) { indexAry[0] = i; indexAry[1] = j; } } } return indexAry; };
let nums = [2, 7, 11, 15]; let target = 9; twoSum(nums,target);
// 暴力解法 A,156 ms | 34.7 MB
var twoSum = function (nums, target) {
for (var i = 0; i < nums.length - 1; ++i) {
for (var j = i + 1; j < nums.length; ++j) {
if (nums[i] + nums[j] == target) {
return [i, j];
}
}
}
}
// 还是没有骚成功的解法 B,124ms | 38.6MB
var twoSum = function (nums, target) {
var maps = {};
for (var i = 0; i < nums.length; ++i) {
if (typeof maps[nums[i]] !== 'undefined') {
maps[nums[i]].push(i);
} else {
maps[nums[i]] = [i];
}
}
nums = nums.sort(function (a, b) { return a - b > 0 ? 1 : -1; })
for (var i = 0; i < nums.length - 1; ++i) {
for (var j = i + 1; j < nums.length; ++j) {
if (nums[i] + nums[j] > target) {
break;
}
if (nums[i] + nums[j] == target) {
return [maps[nums[i]].shift(), maps[nums[j]].shift()];
}
}
}
};
// 在解法B 的基础上优化,86ms | 36.9MB
var twoSum = function (nums, target) {
if (nums.length == 2) return [0, 1];
var maps = {};
for (var i = 0; i < nums.length; ++i) {
if (typeof maps[nums[i]] !== 'undefined') {
maps[nums[i]].push(i);
} else {
maps[nums[i]] = [i];
}
}
for (var i = 0; i < nums.length - 1; ++i) {
var _t = target - nums[i];
if (maps[_t]) {
if (maps[_t].length == 1 && maps[_t][0] == i) continue;
var ix = maps[nums[i]].shift();
var iy = maps[_t].shift();
return ix > iy ? [iy, ix] : [ix, iy];
}
}
};
// 一次hash出结果,最佳题解,80ms | 34.4MB
var twoSum = function (nums, target) {
var maps = {};
for (var i = 0; i < nums.length; ++i) {
var t = target - nums[i];
if (typeof maps[t] !== 'undefined') {
return [maps[t], i];
} else {
maps[nums[i]] = i;
}
}
};