两数之和

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

示例：

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

提示：

• 2 <= nums.length <= 104
• -109 <= nums[i] <= 109
• 只会存在一个有效答案

心路历程

暴力解法

看到题目，第一反应是暴力破解，两层循环，时间复杂度O(n^2)

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function (nums, target) {
  const result = [];
  nums.forEach((item, index) => {
    if (index !== nums.length - 1) {
      nums.forEach((data, key) => {
        if (data + item === target) {
          result.push(index, key);
          return result;
        }
      });
    }
  });
};

聪明的朋友已经看出来，我上面错了好几处地方了：

1.第二层循环应该从第一层的下一个开始，不然可能出现结果都是一个下标的可能

2.result.push(index, key)不该直接push key的，因为第二层不是从nums的第一个开始的

3.在forEach里return是没用的，因为已经在另一个函数体了，最外层的twoSum会始终返回undefined

改正一下上面的代码：

var twoSum = function (nums, target) {
  const result = [];
  nums.forEach((item, index) => {
    if (index != nums.length - 1) {
      nums.slice(index + 1).forEach((data, key) => {
        if (item + data === target) {
          result.push(index, index + key + 1);
          console.log(result);
        }
      });
    }
  });
  return result;
};	

map记录索引

刷题，不是一味追求数量，多看看不同的解法，开拓视野，一生二，二生三，三生万物。我们尝试用map来降低一下时间复杂度。

用map，那么就可以把数字和索引联系在一起，可以快速根据数字找到对应的索引。

这时候有同学说那我们可以先循环一手数组，生成map，然后在遍历map，用target - currentItem得到差值，在用差值到map里去找对应索引，找到就返回出去：

var twoSum = function (nums, target) {
  // 记录item和对应下标
  const indexMap = {};
  for (let i = 0; i < nums.length; i++) {
    const currentItem = nums[i];
    indexMap[currentItem] = i;
  }
  for (const key in indexMap) {
    const difference = target - key;
    if (indexMap[difference] != undefined) {
      return [indexMap[difference], indexMap[key]];
    }
  }
};

大部分用例都可以通过，但是遇到重复数字的就焉了，如[3,3]，最终会返回[1,1]。眼尖的同学说，是以为后来的3把第一个3给顶替掉了，那我们第二次遍历nums，从前到后！但是要加上 indexMap[difference] !== i 的判断，防止一个值重复相加刚好等于target的情况。

var twoSum = function (nums, target) {
  // 记录item和对应下标
  const indexMap = {};
  for (let i = 0; i < nums.length; i++) {
    const currentItem = nums[i];
    indexMap[currentItem] = i;
  }
  for (let i = 0; i < nums.length; i++) {
    const currentItem = nums[i];
    const difference = target - currentItem;
    if (indexMap[difference] != undefined && indexMap[difference] !== i) {
      return [i, indexMap[difference]];
    }
  }
};

map记录之前索引

嘿，你他娘的真是天才！确实可行。那我们在想想有没有不这么麻烦，循环一次就行，嘿，还真有，只需改进一下上面这个同学的代码，循环时就计算差值，然后在map中找对应索引，没有就放入map，有就返回。这样只循环一次还不用担心重复的情况。

var twoSum = function (nums, target) {
  // 记录之前出现过的item和对应下标
  const preIndexMap = {};
  for (let i = 0; i < nums.length; i++) {
    const currentItem = nums[i];
    const difference = target - currentItem;
    const differenceIndex = preIndexMap[difference];
    if (differenceIndex != undefined) {
      return [differenceIndex, i];
    } else {
      // 如果差值下标不存在则将当前item和下标存储到map
      preIndexMap[currentItem] = i;
    }
  }
};

最终代码

var twoSum = function (nums, target) {
  // 记录之前出现过的item和对应下标
  const preIndexMap = {};
  for (let i = 0; i < nums.length; i++) {
    const currentItem = nums[i];
    const difference = target - currentItem;
    const differenceIndex = preIndexMap[difference];
    if (differenceIndex != undefined) {
      return [differenceIndex, i];
    } else {
      // 如果差值下标不存在则将当前item和下标存储到map
      preIndexMap[currentItem] = i;
    }
  }
};

参考链接

• 两数之和