1.两数之和#1

[Givenchy-Coisini]

原题链接

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) 其中 N 是数组中的元素数量。进行了两层for循环，所以时间复杂度为n^2。
• 空间复杂度：O(1) 没有开辟数组本身额外的空间，所以空间复杂度为1。
  写出这种方法是不会让面试官满意的，所以接下来我们要想办法进行优化。

2.借用map

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

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

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

题目要求返回的是数组下标，所以 Map 中的键名是数组元素，键值是索引。
新建一个字典作为婚姻介绍所，nums里的值,逐个来介绍所找对象,没有合适的就先登记着，有合适的就牵手成功。

var twoSum = function (nums, target) {
    const map = new Map();
    for (let i = 0; i < nums.length; i++) {
        const n = nums[i];
        const n2 =target -n;
        if(map.has(n2)){
            // map.get 是获取map中键的值 而数组是1 => 0   2 => 1  右边是index
            return [map.get(n2),i];
        }else {
            // set 的时候 第一个是key 第二个是value
            map.set(n,i)
        }
    }
};

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