LeetCode刷题日志1两数之和

题目：传送门
类别：数组
难度：简单

容易想到的解法

n^2 次循环。第一级循环取数，算得目标数字，第二级看目标数字在不在数组中。最多优化下第二级循环，已经遍历过的就不管了。

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
  for (let i = 0, len = nums.length; i < len; i += 1) {
    const item = nums[i];
    const that = target - item;
    const thatIndex = findIndex(nums, i + 1, that);
    if (thatIndex !== -1) {
      return [i, thatIndex];
    }
  }
};

function findIndex(nums, from, target) {
  for (let i = from, len = nums.length; i < len; i += 1) {
    if (target === nums[i]) {
      return i;
    }
  }
  return -1;
}

最优解

空间换时间。需要一个哈希表。第一级循环取数，算得目标数字，去哈希表看有没有它，有的话结束程序，没有的话存入当前数，key 为当前数，value 为当前 index。

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
  const map = {};
  for (let i = 0, len = nums.length; i < len; i += 1) {
    const item = nums[i];
    const that = target - item;
    const thatIndex = map[that];
    if (thatIndex === undefined) {
      map[item] = i;
    } else {
      return [i, thatIndex];
    }
  }
};

实际测试发现，两个方法内存开销差不多，后者时间开销是前者的一半。