# 1 两数之和

# 题目

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

# 题解

每次循环的时候寻找差值，如果数组里存在这个值，那么就直接返回即可

TIP

执行用时：208 ms, 在所有 JavaScript 提交中击败了 16.79% 的用户
内存消耗：38.8 MB, 在所有 JavaScript 提交中击败了 26.88% 的用户

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    for(let i=0;i<nums.length;i++) {
        let item = nums[i]
        let val = target - item
        if(nums.includes(val)) {
            let second = nums.findIndex(n => n === val)
            if(second !== i) {
                return [i, second]
            }
        }
    }
}

时间复杂度： `O(n^2)`，使用 for循环和 includes/findIndex 方法
空间复杂度： `O(1)`，使用几个变量来保存值
最好情况：尽早的找到值，那么会直接退出循环
最坏情况：在循环的末尾找到值，那么会进行过多的循环

利用 Map 结构，每次循环的时候去里面找值，如果找不到，则把元素作为键，下标作为值存进去

TIP

执行用时：80 ms, 在所有 JavaScript 提交中击败了 89.18% 的用户
内存消耗：39 MB, 在所有 JavaScript 提交中击败了 20.72% 的用户

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    let map = new Map()
    for(let i=0;i<nums.length;i++) {
        let item = nums[i]
        let val = target - item
        if(map.has(val)) {
            return [i, map.get(val)]
        }
        map.set(item, i)
    }
}

时间复杂度： `O(n^2)`，使用 for循环和 has/get 方法
空间复杂度： `O(n)`，使用 map 结构来储存值
最好情况：尽早的找到值，那么会直接退出循环
最坏情况：在循环的末尾找到值，那么会进行过多的循环

基于上面的方法，利用对象获取值为 O(1)的复杂度，减少了判断值的时间

TIP

执行用时：80 ms, 在所有 JavaScript 提交中击败了 89.18% 的用户
内存消耗：38.8 MB, 在所有 JavaScript 提交中击败了 27.24% 的用户

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    let map = {}
    for(let i=0;i<nums.length;i++) {
        let item = nums[i]
        let val = target - item
        if(map[val] != undefined) {
            return [i, map[val]]
        }
        map[item] = i
    }
}

时间复杂度： `O(n)`，使用 for循环，而获取值的复杂度为 `O(1)`
空间复杂度： `O(n)`，使用一个对象结构来储存值
最好情况：尽早的找到值，那么会直接退出循环
最坏情况：在循环的末尾找到值，那么会进行过多的循环

← leetcode for javascript 9 回文数 →