两数之和

let nums = [2, 7, 11, 15, 3, 8]
let target = 19

• 解法一: 双循环嵌套
  • 第一层循环和第二层循环相加如果等于目标值则返回数组 index
• 时间复杂度: O(n²)
  • 假设 arr 中有 n 个元素, 最差的情况计算步数为 n(n - 1) 即 n² - n

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

• 解法二:
  • 用对象存储遍历过后的元素和对应下标
  • 循环 nums 查看对象中是否存在 target - 当前数字的项, 如果存在则返回对象中对应的下标以及当前遍历的 i , 不存在则执行上一步骤
• 时间复杂度: O(n)
  • 用空间换取时间
  • 假设 arr 中有 n 个元素, 最差的情况下计算步数为 n

function twoSum(arr, tar) {
    const preNums = {}
    for(let i = 0; i < arr.length; i++) {
        let curNum = arr[i]
        let tarNum = tar - curNum
        let tarNumIndex = preNums[tarNum]
        if(tarNumIndex !== undefined) {
            return [tarNumIndex, i]
        } else {
            preNums[curNum] = i
        }
    }
}

• 解法三:
  • pop 取出数组最后一项
  • while 循环剩余项并通过 indexOf 来判断是否存在目标值
• 时间复杂度: O(n²)
  • 假设 arr 中有 n 个元素, 最差情况下 while 循环需要 n - 1 次
  • 每次循环 indexOf 正向查找最差情况下需要当前的 arr.length
  • 推理得出步数为 (n - 1) + (n - 2) + ... + 1 即 (n² - n) / 2

function twoSum(arr, tar) {
    let last = arr.pop()
    while(arr.length) {
        if(arr.indexOf(tar - last) > -1) {
            return [arr.indexOf(tar - last), arr.length]
        }
    }
}