两数之和

题目描述

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

示例 1：

输入：nums = [2, 7, 11, 15]，target = 9
输出：[0, 1]

示例 2：

输入：nums = [3, 2, 4]，target = 6
输出：[1, 2]

示例 3：

输入：nums = [3, 3]，target = 6
输出：[0, 1]

暴力枚举

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

  return []
}
复制代码

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

哈希表

function twoSum(nums, target) {
  const map = new Map([
    [nums[0], 0]
  ])

  for (let i = 1; i < nums.length; i++) {
    const num1 = nums[i]
    const num2 = target - num1
    
    if (map.has(num2)) {
      return [map.get(num2), i]
    } else {
      map.set(num1, i)
    }
  }
  
  return []
}
复制代码

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