两数之和

题目

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

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

渣渣思路 - 暴力枚举，双层循环

常规思路我们可能会考虑使用暴力枚举、双层循环的方式，但是算法的时间复杂度是 $O(n^2)$，并不是我们想要的。

/**
 * @description 使用双层循环
 * 
*/
function twoSum(nums: number[], target: number): number[] {
  // 使用双层循环的方式，将每两个数相加
  const len = nums.length

  for (let i = 0; i < len; i++) {
    // 注意这个位置j的初始值是i+1，从当前数开始和后面的数相加
    for (let j = i + 1; j < len; j++) {
        if (nums[i] + nums[j] === target) {
            return [i, j]
        }
    }
  }

  return []
}

常规思路 - 借助哈希表Map

题目的要求是求 两数之和a + b为target，在遍历nums将每个值进行存储记录，假定当前值是a，题目就变成了我们在存储中寻找target - a是否存在

伪代码

存储器 Map

遍历 nums 索引值 i
  if Map 有 target - nums[i] {
    说明有组合
  }

  Map 存储当前值nums[i] 和索引 i

算法实现

/**
 * @descript 借助哈希表Map，转换问题角度
 * 
*/
function twoSum(nums: number[], target: number): number[] {
  // 设置存储器
  const map = new Map<number, number>()
  const len = nums.length

  for (let i = 0; i < len; i++) {
    // 获取差值
    const remain = target - nums[i]

    // 当差值在map中存在时，表示二者之和为target
    if (map.has(remain)) {
      // 返回二者索引
      return [i, map.get(remain)]
    }

    // 将当前值与索引进行存储
    map.set(nums[i], i)
  }

  return []
}

算法时间和空间复杂度

借助哈希表Map实现两数之和，是通过空间换时间的经典实现，将暴力枚举的$O(n^2)$复杂度降低为$O(N)$复杂度

时间复杂度：一次循环遍历，是$O(n)$

空间复杂度：使用Map存储了nums数组元素和索引，是$O(n)$