问题描述

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

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

实例：

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

解决方法

解法一

暴力遍历方法，通过双层遍历，穷尽组合找到两个元素，使之和满足目标值。

原理：双层遍历所有元素，找到 a + b = target 的元素的索引。

时间复杂度为 O(n^2)，空间复杂度为 O(1)。

var twoSum = function(nums, target) {

  for (let i = 0; i < nums.length; i++) {
    const a = nums[i];
    
    for (let j = i + 1; i < nums.length; i++) {
      const b = nums[i];
      if (a + b === target) {
        return [i, j];
      }
    }
  }

  return new Error('there is no answer');
};

解法二

为了快速的查找 target - nums[i] 元素所在的位置，我们可以使用哈希表快速查找元素。比起遍历算法，执行的时间效率为 O(1)。具体实现如下：

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
  const map = new Map();

  nums.forEach((value, index) => {
    map.set(value, index);
  });

  for (let i = 0; i < nums.length; i++) {
    const a = nums[i];
    const residual_value = target - a;
    const j = map.get(residual_value);
    if (j !== undefined && j !== i) {
      return [i, j];
    }
  }

  return new Error('there is no answer');
};

时间复杂度为 O(n)，空间复杂度为 O(n)。

解法三

仍然是使用哈希表找元素，但是只使用一次哈希。

var twoSum = function(nums, target) {

  const map = new Map();

  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i];

    if (map.get(complement)) {
      return [map.get(complement), i];
    }
    
    map.set(nums[i], i);
  }

  return new Error('there is no answer');
};

参考文档

• Leetcode - 两数之合