LeetCode.1 两数之和(Two Sum)

开坑,以后每周刷一两道LeetCode
1、题目
两数之和:

给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。
示例
给定 nums = [2, 7, 11, 15], target = 9因为 nums[0] + nums[1] = 2 + 7 = 9所以返回 [0, 1]

2、优秀答案
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function(nums, target) {
const comp = {};
for(let i=0; i<nums.length; i++){
if(comp[target – nums[i] ]>=0){
return [ comp[target – nums[i] ] , i]
}
comp[nums[i]] = i
}
};
遍历数组,定义一个对象,对象属性的key是顺序遍历中数组项的value,对象属性的value是数组项的下标
comp[target-nums[i]] = i
一旦存在对象中target-nums[i]属性的值(即数组项的下标)大于0,即存在数组中两数之和等于target
if(comp[target – nums[i] ]>=0){
return [ comp[target – nums[i] ] , i]
}
我还能说什么,map掌握得炉火纯青。
3、我的答案
公开处刑现场
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function (nums, target) {
function isEqualToTarget(num1, num2) {
if (num1 + num2 === target) {
return true
} else {
return false
}
}

function findTargetItem(arr, oldArr) {
for (let i = 0; i < arr.length – 1; i++) {
for (let j = i + 1; j < arr.length; j++) {
if (isEqualToTarget(arr[i], arr[j])) {
return [oldArr.indexOf(arr[i]), oldArr.length – 1 – oldArr.reverse().indexOf(arr[j])]
}
}
}
}
const oldArray = nums.slice(0)
nums.sort((a, b) => a – b)
let tailIndex = nums.findIndex((value, index) => {
return value >= target – nums[0] && index !== 0
})
if (tailIndex === -1) { // [5, 7, 11, 12] 18
return findTargetItem(nums, oldArray)
} else if (isEqualToTarget(nums[0], nums[tailIndex])) {
return [oldArray.indexOf(nums[0]), oldArray.length – 1 – oldArray.reverse().indexOf(nums[tailIndex])]
} else {
nums.length = tailIndex + 1
return findTargetItem(nums, oldArray)
}
};
当时写的主要想法依然是暴力遍历,只不过做了一丁点儿优化
nums.sort((a, b) => a – b)
let tailIndex = nums.findIndex((value, index) => {
return value >= target – nums[0] && index !== 0
})
先从小到大排序,然后去掉与数组最小值相加大于target的值。这个过程算优化吧/捂脸好歹战胜70%多的提交记录,还有继续的勇气
4、路漫漫其修远兮

评论

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

这个站点使用 Akismet 来减少垃圾评论。了解你的评论数据如何被处理