[LeetCode] 1.两数之和 —— JS解法

一、题目

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

二、题目来源

• 力扣（LeetCode）

三、解题方法

1. 两层for循环的解法

// 116 ms,38 M
var twoSum = function(nums, target) {
    let result = []
    for (let i = 0; i < nums.length; i++) {
        let num1 = nums[i]
        let num2 = target - num1
        for (let j = i + 1; j < nums.length; j++) {
            if (num2 === nums[j]) {
                result = [i, j]
            }
        }
    }
    return result
}

想着优化一下，于是写成了下面这样，结果并没有更好……

// 184 ms, 39.9 M
var twoSum = function(nums, target) {
    let result = []
    let numsCopy = [...nums]
    for (let i = 0; i < nums.length; i++) {
        let num1 = nums[i]
        let num2 = target - num1
        numsCopy.splice(0, 1)
        if (numsCopy.includes(num2)) {
            result = [nums.indexOf(num1), numsCopy.indexOf(num2) + i + 1]
            break
        }
    }
    return result
}

2. map的解法

// 88 ms, 40.2 MB
var twoSum = function(nums, target) {
    let map = new Map();
    for (let i = 0; i < nums.length; i++) {
        if (!map.has(target - nums[i])) {
            map.set(nums[i], i);
        } else {
            return [map.get(target - nums[i]), i]
        }
    }
}

3. obj的解法

// 80 ms,40.2 MB
var twoSum = function(nums, target) {
    const obj = {}
    for (let i = 0; i < nums.length; i++) {
        if (obj[target - nums[i]] !== undefined) {
            return [obj[target - nums[i]], 1]
        }
        obj[nums[i]] = i
    }
}

4. 递归的解法

// 80 ms，41.3 MB
var twoSum = function(nums, target, i = 0, maps = {}) {
    const map = maps
    if (map[target - nums[i]] >= 0) {
        return [map[target - nums[i]], i]
    } else {
        map[nums[i]] = i;
        i++
        if (i < nums.length) {
            return twoSum(nums, target, i, map)
        }
    }
}