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.

翻譯

給定一個整數數組 nums 和一個整數 target ，傳回兩個數字的索引，使它們相加為 target 。 您可以假設每個輸入都有一個解決方案，並且您不能兩次使用相同的元素。 您可以按任意順序返回答案。

測試資料

Example 1: 範例 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: 範例 2：

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

Output: [1,2]

Example 3: 範例 3：

Input: nums = [3,3], target = 6

Output: [0,1]

解題思路

這題簡單是簡單 但一個元素一個一個匹配會需要兩個迴圈 會需要 O(n^2)時間複雜度 希望這題可以降到 O(n)

將元素數值當作 key 索引當作 value 製作一個 map，然後將 target - 目前的數值 得出的數值就可以在 map 裡搜尋 key

程式碼

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

  for (let i = 0; i < nums.length; i++) {
    map.set(nums[i], i);
  }

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

//nums = [2,7,11,15], target = 9
console.log(twoSum([1, 3, 4, 2], 6));