#1 Two Sum

當需要 search 時善用 Map 降低時間複雜度

題目連結在此

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.

nums[] 裡哪兩個數字總和等於 target
output: 符合條件兩個值的 index 位置

Example:

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

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

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

var twoSum = function(nums, target) {
  
};

Edge Case

• 值是負數

• 是否有排序 (看起來沒有，因為有排序的話有很簡單方法就可以有解答)

• 可能有重覆值

• 兩個以上答案、 nums.length < 2，根本無法相加 (題目說不會發生)

哪種資料結構解

• 第一直覺會想到 Array

• i = 0 時， i[0] = 2, 所以我們要找的就是 9 - 2，所以我想要 indexOf( 9 - 2)，看看有沒有。

• 都找不到的話 i++，再重覆以上

var twoSum = function(nums, target) {
    const len = nums.length;
    for(let i = 0; i< len; i++ ){
        var ind = nums.indexOf(target - nums[i]);
        if(ind !== -1 && i !== ind){
            return [i, ind];
        }
    }

};

但這樣解是 Big(n²) 以上，所以一定會有更好解法

改善

因為沒排序所以也不能用 Binary Search。我們其實是想要做 "Search" 所以 Map 會是更好做法。因為 Map 在尋找跟增加效能都比 Array 好，而且時間複雜度也降到接近 Big O(n)

var twoSum = function(nums, target) {
    const m = new Map();
    let result;
    nums.forEach( (item, index) => {
        let indValue = target - item;
        if (m.has(indValue)) {
            result = [m.get(indValue), index];
        }
        m.set(item, index);
    })
    return result;
};

Runtime: 52 ms, faster than 92.70% of JavaScript online submissions for Two Sum.

學到什麼?

• 回 傳什麼通常都蠻重要，會影響思考方向，這題是回傳 index

• 換位思考。想想除了你直覺想到解法有沒有別的更好，例如 two pointer、 ，想不到的話此題是不是可以用 map 取代 Array 讓時間複雜度變低?