LeetCode Js-1. Two Sum

    AllenLi
    LeetCode Js-Array

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

    提供指定數組與一個整數目標，回傳兩個數字相加等於目標的陣列位置。

    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]

    Solution:
    1. 想像數組的陣列為一區塊
    2. 用「for迴圈」將目標值與陣列依序判斷
    3.「if條件」將目標值減去數組中的數字並判斷是否未定義
    true:不是未定義，回傳[對應 hashTable 中值的位置 , 回合數]
    false:是未定義，將比對回合數放入 hashTable 中對應數組位置
    ex.詳情請閱FlowChart

    Code 1:

    var twoSum = function (nums: number[], target: number): number[] {
  const hashTable: Record<string, number> = {};
  for (let i = 0; i < nums.length; i++) {
    if (hashTable[target - nums[i]] !== undefined) {
      return [hashTable[target - nums[i]], i];
    } else {
      hashTable[nums[i]] = i;
    }
  }
  return [];
};

    FlowChart:
    Example 1

    Input: nums = [2, 7, 11, 15], target = 9
i = 0  1   2   3
      2   7   11  15

step.1
hashTable = {} // 初始為空物件
i = 0; nums[i] = 2;
if ((hashTable[9 - 2]) === undefined) // hashTable[7] 不存在
hashTable[nums[i]] = i; // 將 2 的索引存入 hashTable，結果：hashTable = { '2': 0 }

step.2
hashTable = { 2: 0 } 
i = 1; nums[1] = 7;
if ((hashTable[9 - 7]) !== undefined) // hashTable[2] 存在，且值為 0
return ([hashTable[9 - 7], 1]); // 返回 [0, 1]

    Remark: 暴力解 => for{nums[i]} > for{nums[j]} > if{i + j = target}，return [i, j]。(雙迴圈的時間複雜度是O(n^2))

    var twoSum = function(nums, target) {
    const box = {};
    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]
            }
        }
    }
};

    Code 2: map + forEach

    var twoSum = function (nums: number[], target: number): number[] {
  const indexMap: Map<number, number> = new Map();
  let result: number[] = [];

  nums.forEach((num, index) => {
    const complement = target - num;

    if (indexMap.has(complement)) {
      result = [indexMap.get(complement)!, index];
    }
    indexMap.set(num, index);
  });
  return result;
};

    Related Posts