1.JavaScript LeetCode 1-两数之和、 Two Sum，2021-04-15

发布于 2022年 01月 13日 08:04

1. JavaScript LeetCode 1: 两数之和 | Two Sum

LeetCode第一题
来源：力扣（LeetCode）
链接：leetcode-cn.com/problems/tw…

题目描述

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

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

题解、思路

该题为LeetCode第一题，也是前端面试中出现频率较高的题，较为基础，该题目前我有两种思路，一种为追求时间复杂度，一种为追求空间复杂度，一般看到这道题，第一时间想到的就是循环两遍，这样做空间复杂度低但是时间复杂度高，有时面试也会遇到面试官限制时间复杂度，毕竟会运行的更快嘛。

循环两遍，时间复杂度O(n²)

循环两遍的思路没什么可解释的，就是循环两遍，然后判断第一遍和第二遍相加时是否等于目标值。

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function (nums, target) {
  for (var i = 0; i < nums.length; i++) {
    for (var j = i + 1; j < nums.length; j++) {
      if (nums[i] + nums[j] === target) {
        return [i, j]
      }
    }
  }
};

循环一遍利用Map对象 时间复杂度 O(n)

利用Map对象保存键值对的特性，并配合Map对象的set,get,has方法较为方便，也可以选择使用对象(Object)
思路就是循环时判断Map对象里是否存在目标值与当前值的差值如果有就使用get从Map对象里取出，如果没有则Set进Map对象， 把当前值作为key，下标作为value

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
 var twoSum = function(nums, target) {
    // 创建一个Map对象
    const m = new Map();
    for(let i = 0; i < nums.length; i++){
        // 判断是否存在循环到当前数组的值与目标值的差值
        if(m.has(target - nums[i])){
            // 有就从Map对象里取出
            return [m.get(target - nums[i]), i]
        }
        // 没有则存入Map对象
        m.set(nums[i], i)
    }
  };

循环一遍使用Object模拟Map 时间复杂度O(n)

使用对象的思路和使用Map对象的思路大体一致，只不过对象没有Map那么多的方法。
循环时判断对象是否存在目标值与当前值的差值的key，如果有则返回，没有则存入对象

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    // 创建一个对象
    let obj = {}
    for (let i = 0; i < nums.length; i++) {
        // 判断对象的key是否存在当前值与目标值的差值
        if(obj[target - nums[i]] !== undefined) {
            // 如果存在则返回
            return [obj[target - nums[i]], i]
        }
        // 没有则存入对象
        obj[nums[i]] = i
    } 
};

突然想到，还可以使用indexOf方法配合Map对象去做，不过这样就时间复杂度又提升了，但应该能做到最少行数。。
距离上次发文章过去三个月了，对自己真是无语死，一点不自律，也没有任何沉淀和积累，单词也没坚持下去，本来准备持续更新的superMap组件也因为懒停掉了。什么时候才能自驱啊！！

推荐文章