Leetcode - Easy - 1. Two Sum - Javascript

Leetcode - Easy - 1. Two Sum - Javascript

   清晨7:57       Rain Lin

---

 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].

Constraints:

• 2 <= nums.length <= 104
• -109 <= nums[i] <= 109
• -109 <= target <= 109
• Only one valid answer exists.

 

Follow-up: Can you come up with an algorithm that is less than O(n2) time complexity?

解題方向：

1. 用兩個 for loop 交叉比對找到正確的兩個值, 但這樣的複雜度是 O(n2), 所以應該不是這種做法

2. 透過 dictionary 方式, key 為數值, value 為 index, 用兩個 for loop 即可找到正確的配對  O(2n)

解題注意地方：

1. 先把數值轉成 dict key, value 是 index

2. dict 是 undefined, 需要跳過

3. 找到的 index 是自己, 也要跳過

程式碼：

/**

 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */


var twoSum = function(nums, target) {
    const numlen = nums.length;
    let dictNum = {};
    
    for (let i = 0; i < numlen; i++) {
        dictNum[nums[i]] = i;
    }    

    for (let i = 0; i < numlen; i++) {
        const leftVal = target - nums[i];
        
        if (dictNum[leftVal] !== undefined && dictNum[leftVal] !== i) {
            return [i, dictNum[leftVal]]
        }
    }
};

執行成果：