0001_Leetcode_1 两数之和【简单】

命名规则：AAA_Leetcode_BBB XXX【YYY】 AAA表示第N篇，BBB表示Leetcode中的第N道题，XXX是标题，YYY是力扣中的难度等级。

万事开头难，从简单的开始

题目:

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

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

解法一：穷举法

思路描述：最简单的方方法就是每个元素都都加一次去判断。

  for (let i = 0;i<nums.length;i++){
    let num1 = nums[i]
    for (let j = 0;j<nums.length;j++){
      let num2 = nums[j]
      if((num1 + num2 === target) && (i !== j)){
        return [i,j]
      }
    }
  }

这个代码还可以进一步优化，比如对于加法来说a+b和b+a是一样，那这样的遍历方式就有重复遍历的情况，第二个可优化为let j = i + 1，这样底下的i !==j也可以不写了。即使这样时间复杂度仍然是O(n²)，空间复杂度是O(1)

解法二：查表法

思路描述：每遍历到一个元素就去记录一下，这样遍历下一个元素的时候就可以快速查找（记录要使用易查的方式，比如哈希表等，而不是用数组去记录，数组的特点是有序，但查找慢）

 const len = nums.length

  const map = new Map()
  map.set(target - nums[0],0)

  for(let i = 1;i<len;i++){
    const key = nums[i]
    const dif = map.get(key);
    if (dif !== undefined){
      return [dif,i]
    }else {
      map.set(target -nums[i] ,i)
    }
  }

这样的算法时间复杂度降到了O(n)，空间复杂度是O(n)，用空间换时间