ccDocs

外观

导航栏

两数之和 简单 ​

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

1. 暴力枚举 ​

1.1 思路 ​

通过双层遍历，消耗的时间复杂度为O(n^2)，空间复杂度为O(1)。

1.2 代码 ​

js
// 暴力枚举

const twoSum = function (nums, target) {
    for(let i = 0; i < nums.length; i++){
        for(let j = i + 1;j < nums.length; j++){
            if(target - nums[i] === nums[j]){
                return [i,j] // 返回下标
            }
        }
    }

    console.log("no two sum solution")
}

const nums = [1,2,5,3]
console.log(twoSum(nums, 8)) // 下标： 2 3

1.3 结果 ​

  • 时间复杂度：O(n^2)
  • 空间复杂度：O(1)

2. 散列表 ​

2.1 思路 ​

  • 通过散列表，将数组中的值存储起来，然后通过散列表的查找，来判断是否存在目标值。

2.2 代码 ​

js
// 散列表

const twoSum2 = function (nums, target) {
    const map = new Map() // 存储循环值
    for(let i = 0; i < nums.length; i++){
        const complement = target - nums[i]

        if(map.has(complement)){
            return [map.get(complement), i]
        }
        map.set(nums[i], i)
    }

    console.log("no two sum solution")
}

const nums2 = [1,2,5,3]
console.log(twoSum2(nums, 8)) // 下标： 2 3

2.3 结果 ​

  • 时间复杂度：O(n)
  • 空间复杂度：O(n)