📝4-算法 - 两数之和

✊ 作者： 七弦 ✊不积跬步，无以至千里；不积小流，无以成江海。 ✊ 时间：2021.07.22 ✊ 题目来源： 力扣 - 2

1. 题目说明

2.1 暴力枚举法

时间复杂度：O(n2) 空间复杂度：O(1)

var twoSum = function(nums, target) {
    for (let i = 0; i < nums.length; i++) {
        const x = nums[i];
        for (let j = i + 1; j < nums.length; j++) {
            if (nums[j] == target - x) {
                return [i, j]
            }
        }
    }
    return []
};

2.2 静态hash表

时间复杂度：O(n) 空间复杂度：O(n) 空间换时间

var twoSum = function(nums, target) {
    const map = new Map()
    nums.forEach((num, i) => map.set(num, i))
    for (let i = 0; i < nums.length; i++) {
        const x = nums[i];
        if (map.has(target - x)) {
            const index = map.get(target - x)
            if (i != index) return [i, index]
        }
    }
    return []
};

2.3 动态hash表

时间复杂度：O(n) 空间复杂度：O(n) 空间换时间

var twoSum = function(nums, target) {
    const map = new Map()
    for (let i = 0; i < nums.length; i++) {
        const x = nums[i];
        if (map.has(target - x)) {
            const index = map.get(target - x)
            return [i, index]
        }
        map.set(x, i)
    }
    return []
};