日期：2020-9-3
题目描述：https://leetcode-cn.com/problems/two-sum/

方法一：暴力法

强行遍历，target与nums的差值是否在数组中。
实现：

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

复杂度分析：
时间复杂度：O(**n2)**
对于每个元素，我们试图通过遍历数组的其余部分来寻找它所对应的目标元素，这将耗费 O(n) 的时间。因此时间复杂度为 O(_n_2)。
空间复杂度：O(1)。
**

方法二：一遍哈希表

用目标数减去当前数得到要找的数当做下标，
如果map里有要找的数则说明两数都找到了对应解，并立即将其返回

var twoSum = function(nums, target) {
    let sumMap = new Map();
    for (let i = nums.length - 1; i >= 0; i--) {
        if (sumMap.has(nums[i])) return [i, sumMap.get(nums[i])];
        let dif = target - nums[i];
        sumMap.set(dif, i);
    }
};

复杂度分析：
时间复杂度：O(n)，
我们只遍历了包含有 nn 个元素的列表一次。在表中进行的每次查找只花费 O(1) 的时间。
空间复杂度：O(n)，
所需的额外空间取决于哈希表中存储的元素数量，该表最多需要存储 n 个元素。