1.两数之和

[Geekhyt]

原题链接

1.暴力法

符合第一直觉的暴力法，潜意识里要学会将两数之和转换为两数之差。

然后问题就变得像切菜一样简单了，双层循环找出当前数组中符合条件的两个元素，并将它们的索引下标组合成数组返回即所求。

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

• 时间复杂度：O(n^2)
• 空间复杂度：O(1)

写出这种方法是不会让面试官满意的，所以接下来我们要想办法进行优化。

2.借用 Map

算法优化的核心方针基本上都是用空间换时间。

我们可以借用 Map 存储遍历过的元素及其索引，每遍历一个元素时，去 Map 中查看是否存在满足要求的元素。

如果存在的话将其对应的索引从 Map 中取出和当前索引值组合为数组返回即为所求，如果不存在则将当前值作为键，当前索引作为值存入。

题目要求返回的是数组下标，所以 Map 中的键名是数组元素，键值是索引。

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

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