# [LeetCode 1] 从暴力到优雅——两数之和的JavaScript实现

我一直相信“注释即文档”,所以思路和运行结果都在注释里写了。

这道题最直接的思路,肯定就是暴力遍历了。没有什么是循环解决不了的,如果有,就再循环一次:

/**
 * 无优化的暴力遍历,O(n^2)
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 * ------result------
 * memory: 34.6 MB (40%)
 * speed: 260 ms   (20%)
 */
var twoSum1 = function (nums, target) {
  for (let i = 0; i < nums.length; ++i) {
    for (let j = 0; j < nums.length; ++j) {
      if (i === j) continue;
      if (nums[i] + nums[j] === target) return [i, j];
    }
  }
};

但是这个思路显然有问题,直接遍历会有重复:2+7=9,7+2还是=9。所以每次循环之前,去掉已经遍历过的:

/**
 * 优化后的暴力遍历,O((n^2 + n) / 2)
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 * ------result------
 * memory: 34.6 MB (40%)
 * speed: 156 ms   (60%)
 */
var twoSum2 = function (nums, target) {
  for (let i = 0; i < nums.length; ++i) {
    for (let j = i + 1; j < nums.length; ++j) {
      if (nums[i] + nums[j] === target) return [i, j];
    }
  }
};

仔细想想,这道题的难点在哪,求和吗?显然不是。这道题的难点在“找“,也就是怎么找到符合要求的两个数的下标。因为直接遍历相当于是同时找两个数的下标(因为在循环之前i,j都不确定),如果只找一个数的下标,肯定能省不少事;但是加法肯定是需要两个操作数的,所以我们可以换个思路,改用减法,这样在每次循环之前就可以确定一个下标(通过检查target-nums[i]是否存在于nums中,将变量从i,j变成j,相当于确定了一个下标i)。

确定了减法的思路之后,再看看有什么可以改进的地方。首先,直接遍历找下标效率是很低的,那么不妨试试原生的indexOf方法,看看原生的函数有没有什么优化:

/**
 * 检查target-nums[i]是否存在于nums中
 * 理论上复杂度为O(n),因为只进行一次遍历,但实际复杂度取决于indexOf的实现
 * 所以总体复杂度还是O(n^2),并且实际表现不比优化后的暴力遍历好
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 * ------result------
 * memory: 34.7 MB (40%)
 * speed: 212 ms   (30%)
 */
var twoSum3 = function (nums, target) {
  for (let i = 0; i < nums.length; ++i) {
    const j = nums.indexOf(target - nums[i]);
    if (~j && i !== j) return [i, j];
  }
};

原生的indexOf效率居然并不比直接遍历高。查看MDN上的文档可以看到(这里就不赘述了),indexOf的实现其实也是循环,而且因为考虑到各种不同类型,所以加了很多额外的代码,慢也正常。考虑到我们这里只有数字,所以不妨进行一些简化:

/**
 * 原生的indexOf为了可靠降低了效率,所以针对具体情况进行简化
 * 总体复杂度还是O(n^2),但比优化后的暴力遍历稍好
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 * ------result------
 * memory: 34.4 MB (70%)
 * speed: 144 ms   (60%)
 */
var twoSum4 = function (nums, target) {
  for (let i = 0; i < nums.length; ++i) {
    const j = indexOf(nums, target - nums[i]);
    if (~j && i !== j) return [i, j];
  }

  function indexOf(arr, el) {
    for (let i = 0; i < arr.length; ++i) {
      if (arr[i] === el) return i;
    }
    return -1;
  }
};

可以看到有了明显的效率提升。

还有没有什么提升空间?直接遍历总归还是不那么优雅(可能好处在不会增加空间复杂度,因为基本不需要额外空间),所以我们就会很自然地想到用空间换时间,提前用一个表把数字和下标的映射存好,到时候直接去取(这时候开销近似于O(1)),就省去了遍历的时间。这种情况在Java里有HashMap,但在JS里没有,所以就用对象凑合一下,反正也是键值对:

/**
 * 总体思路不变,但这次用空间换时间,类似于HashMap的实现,提高查找效率
 * 这次的时间复杂度是O(2n),一次遍历建立Map,一次遍历找到结果;但空间复杂度上升到O(n)
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 * ------result------
 * memory: 35.9 MB (10%)
 * speed: 80 ms    (90%)
 */
var twoSum5 = function (nums, target) {
  const numToIndexMap = {};
  for (let i = 0; i < nums.length; ++i) {
    numToIndexMap[nums[i]] = i;
  }
  for (let i = 0; i < nums.length; ++i) {
    const j = numToIndexMap[target - nums[i]];
    if (j && j !== i) return [i, j];
  }
};

但是这个还是差一点,因为需要遍历两遍,一遍建立Map一遍获取结果。能不能一边遍历一边判断呢?答案是可以的。此外,因为这题的一个要求,不能重复使用某一个数,所以还有一点小小的优化,就是先判断是否相等,然后往Map里添加,这样可以省掉判断是否相等的这一点点开销:

/**
 * 进一步提高查找效率,建立Map的同时进行遍历,只需要进行一次遍历,同时还可以避免把自己算进去的开销
 * 这次的时间复杂度是O(n),空间复杂度还是O(n)
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 * ------result------
 * memory: 35.4 MB (10%)
 * speed: 72 ms    (97.6%)
 */
var twoSum6 = function (nums, target) {
  const numToIndexMap = {};
  for (let i = 0; i < nums.length; ++i) {
    const j = numToIndexMap[target - nums[i]];
    if (j != null) return [j, i]; // 区分0和undefined,0也是falsy value;同时还要注意顺序
    numToIndexMap[nums[i]] = i;
  }
};

从ES6开始,JS里有了真正的Map。我们不妨把自己写的Map换成原生的Map:

/**
 * 如果换成真正的Map呢?
 * 从结果中可以看出,原生的Map在空间上似乎有更好的优化。
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 * ------result------s
 * memory: 34.4 MB (80%)
 * speed: 72 ms    (97.6%)
 */
var twoSum7 = function (nums, target) {
  const numToIndexMap = new Map();
  for (let i = 0; i < nums.length; ++i) {
    const j = numToIndexMap[target - nums[i]];
    if (j != null) return [j, i];
    numToIndexMap[nums[i]] = i;
  }
};

可以看出,原生的Map在空间上有了优化,从一定程度上解决了空间开销大的问题。

最后更新于: 6/25/2020, 2:10:06 PM