1. Two Sum - LeetCode

紀錄 two sum 的解題過程以及解題思緒

1. Two Sum

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.



Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].
Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]
Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]

兩個迴圈

首先閱讀完第一個題目我的直覺是兩個迴圈來處理

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = 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 && i !== j) {
        return [i, j];
      }
    }
  }
};

改進兩個迴圈

接著觀察一下發現遍歷的過程中，在內層的那層迴圈中其實頭幾個是不需要算了，因為在更前面的外層迴圈中其實是驗證過的

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = 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];
      }
    }
  }
};

但這樣的時間複雜度還是 O(n²) ，參考別人的解法後用 HashMap 做出了 O(n) 的解法

HashMap

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function (nums, target) {
  const hash = {};
  for (let i = 0; i < nums.length; i++) {
    let num1 = nums[i];
    let num2 = target - num1;
    if (typeof hash[num2] !== 'undefined') {
      return [hash[num2], i];
    }

    hash[num1] = i;
  }
};

來試著解析一下，首先我們是要在 array 中尋找兩個數加起來等於 target

nums[i] + nums[j] = target

換句話說

target - nums[i] = nums[j]

那怎麼利用 HashMap 跟剛剛的思考方向解題，首先在遍歷 array 的過程中並且紀錄下所需要的補數及 index

var twoSum = function (nums, target) {
  const hash = {};
  for (let i = 0; i < nums.length; i++) {
    let num1 = nums[i];
    let num2 = target - num1;
    if (typeof hash[num2] !== 'undefined') {
      return [hash[num2], i];
    }

    hash[num1] = i;
  }
};

// 定義出 array 中的數跟它所需的補數
let num1 = nums[i];
let num2 = target - num1;

// 如果發現 HashMap 中有補數，代表這個補數有出現在這個 array 並且在前面遍歷過了
if (typeof hash[num2] !== 'undefined') {
  return [hash[num2], i];
}

// 把 array 中的數及 index 當作 kay-value 放入 HashMap
hash[num1] = i;