1. 两数之和了解算法复杂度

1.这是leetcode第一题， https://leetcode.cn/problems/two-sum/ ， 两数之和。

image.png

首先最简单暴力的方式，就是双重for循环，如果两者相加等于target，那么我们就return出去。

//数组长度是n，双重循环，  时间复杂度On²， 空间复杂度O(1)
var twoSum = function (nums, target) {
    for (let i = 0; i < nums.length; i++) {
        for (let j = 0; j < nums.length; j++) {
            if (i !== j && nums[i] + nums[j] === target) {
                return [i, j]
            }
        }
    }
};

然后再来讲讲更好的一个解决思路，其实我们可以类比生活中的例子，匹配的原则， 例如我是2，我知道我们的结局是9，那么我就只需要找到7，其它的我不用关心。 那么我们就需要一个表来记录，每一次有数字进来，如果在这个表里面有他们当前可以匹配的数字，那么就配对成功了，如果没有匹配的我就记录他需要匹配的数字是多少。

//数组长度n ， 时间复杂度 On, 空间复杂度On
var twoSum = function (nums, target) {
    let obj = {};
    for (let i = 0; i < nums.length; i++) {
        let num = nums[i];
        let n = target - num;

        if (num in obj) {
            return [i, obj[num]];
        } else {
            obj[n] = i
        }
    }
};