問題描述

給定一個(gè)整數(shù)數(shù)組 nums 和一個(gè)目標(biāo)值 target，請你在該數(shù)組中找出和為目標(biāo)值的那 兩個(gè) 整數(shù)，并返回他們的數(shù)組下標(biāo)。

你可以假設(shè)每種輸入只會(huì)對應(yīng)一個(gè)答案。但是，你不能重復(fù)利用這個(gè)數(shù)組中同樣的元素。

實(shí)例：

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

因?yàn)?nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

解決方法

解法一

暴力遍歷方法，通過雙層遍歷，窮盡組合找到兩個(gè)元素，使之和滿足目標(biāo)值。

原理：雙層遍歷所有元素，找到 a + b = target 的元素的索引。

時(shí)間復(fù)雜度為 O(n^2)，空間復(fù)雜度為 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] 元素所在的位置，我們可以使用哈希表快速查找元素。比起遍歷算法，執(zhí)行的時(shí)間效率為 O(1)。具體實(shí)現(xiàn)如下：

/**
 * @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');
};

時(shí)間復(fù)雜度為 O(n)，空間復(fù)雜度為 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 - 兩數(shù)之合