LeetCode - Two Sum

Image From LeetCode

今天我們要講解的是 [Two Sum]，這在 LeetCode 算是比較簡單的題目，讓我們一起開始吧！

進來之前請先注意，我的方式不一定完全正確，只是依照我自己的理念進行撰寫，所以如果程式上有什麼更好的解法，歡迎提出見解。

這次題目

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

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

Example

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

自己解法

預期一開始原本想說用兩層 For 迴圈去解，雖然能確實解出來，但問題在效能上卻掉了好幾個百分比，複雜度 O(n)，當內容越多也代表要處理的時間越久，所以我透過鍵值的方式去確認值是否存在，如下：

初始他會給你預設值，要你在下方的twoSum進行處理接著回傳回去。

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

初步我們建立陣列，用來放置參數值，依照題目參考的nums會依照結果來命名 key 值，接著建立回傳的數值，記得設定let讓他可被更改。

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function (nums, target) {
  // 紀錄已被拿出過得值
  const mapNumber = {};
  // 最終回傳得值
  let mapCount = [];
};

接著我們透過For迴圈來比對資料，並且把目前選擇的內容丟到num的參數。

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function (nums, target) {
  // 紀錄已被拿出過得值
  const mapNumber = {};
  // 最終回傳得值
  let mapCount = [];
  for (let i = 0; i < nums.length; i++) {
    // 當前的值
    let num = nums[i];
  }
};

接著我們取得需要的值，就完成，說明如下：

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function (nums, target) {
  // 紀錄已被拿出過得值
  const mapNumber = {};
  // 最終回傳得值
  let mapCount = [];
  for (let i = 0; i < nums.length; i++) {
    // 當前的值
    let num = nums[i];

    /**
     * x + y = ans
     * 所以 => y = ans - x
     * 範例
     *    => 2 + y = 9
     *    => y = 9 - 2
     * 測試就會如下方則的targetNum
     *
     * 另外有個小問題，因為產生的物件是字串格式，
     * 所以我們要透過toString進行轉換。
     */
    let targetNum = (target - num).toString();
    // 接著確認mapNumber是否有y的物件，如果沒有就針對2去產生當下的值。
    if (mapNumber[targetNum] !== undefined) {
      // 此時發現 y = 9 - x ，並且確認是有值那就回傳當前的key值。
      return [mapNumber[target - num], i];
    } else {
      // 在這我們用值去當key，並且把key設定為值，這樣就能像上面去取得資料。
      mapNumber[num] = i;
    }
  }
};

實作結果

最後再提交就能得出下面的結果，雖然我的不一定是最好解法，但能解決複雜度的問題，如果有更好的解法歡迎一起討論，我們下一個挑戰見！

Two Sum