算法题目整理分析--两数之和

题目如下:

方法一:

最简单粗暴直接的方式,就是两层遍历。

时间复杂度O(n2),空间复杂度O(1)

function getNumbers(nums,target){
    let result = []
    nums.forEach((item, idx) => {
        nums.forEach((itemIn, idxIn) => {
            if (idx === idxIn) {
                return
            }
            if ((item + itemIn) === target) {
                result = [idx, idxIn]
            }
        })
    })
    return result
}

简单直接,同样也没有技术性可言。

方法二:两遍哈希表

首先创建哈希表,然后遍历数组。遍历过程中如果发现匹配的,则直接返回。

时间复杂度O(n),空间复杂度O(n)

function getNumbers(nums,target){
    let result = []
    let hash = {}

    for (let i = 0; i < nums.length; i++) {
        hash[nums[i]] = i
    }
    for (let i = 0; i < nums.length; i++) {
        let num = target - nums[i]
        if (hash.hasOwnProperty(num) && hash[num] !== i) {
            result = [hash[num], i]
        }
    }
    return result
}

方法三:一遍哈希表

一遍遍历,遍历的同时创建哈希,时间复杂度变成了O(n),空间复杂度O(n)

function getNumbers(nums,target){
    let result = []
    let hash = {}

    for (let i = 0; i < nums.length; i++) {
        let num = target - nums[i]
        if (hash.hasOwnProperty(num) && hash[num] !== i) {
            result = [hash[num], i]
        }
        hash[nums[i]] = i
    }
    return result
}

随机浏览