✊ 作者： 七弦 ✊不积跬步，无以至千里；不积小流，无以成江海。 ✊ 时间：2021.07.12 ✊ 题目来源： 力扣 - 1

1. 题目说明

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
示例 1：

  1. 输入：nums = [2,7,11,15], target = 9
  2. 输出：[0,1]
  3. 解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

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

示例 3：

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

2. 题目解决

2.1 暴力枚举法

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

  1. var twoSum = function(nums, target) {
  2.     for (let i = 0; i < nums.length; i++) {
  3.         const x = nums[i];
  4.         for (let j = i + 1; j < nums.length; j++) {
  5.             if (nums[j] == target - x) {
  6.                 return [i, j]
  7.             }
  8.         }
  9.     }
  10.     return []
  11. };

2.2 静态hash表

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

  1. var twoSum = function(nums, target) {
  2.     const map = new Map()
  3.     nums.forEach((num, i) => map.set(num, i))
  5.     for (let i = 0; i < nums.length; i++) {
  6.         const x = nums[i];
  7.         if (map.has(target - x)) {
  8.             const index = map.get(target - x)
  9.             if (i != index) return [i, index]
  10.         }
  11.     }
  13.     return []
  14. };

2.3 动态hash表

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

  1. var twoSum = function(nums, target) {
  2.     const map = new Map()
  4.     for (let i = 0; i < nums.length; i++) {
  5.         const x = nums[i];
  6.         if (map.has(target - x)) {
  7.             const index = map.get(target - x)
  8.             return [i, index]
  9.         }
  10.         map.set(x, i)
  11.     }
  13.     return []
  14. };