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

# #1 Two Sum

[題目連結在此](https://leetcode.com/problems/two-sum/)

```
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

* 值是負數&#x20;
* 是否有排序 (看起來沒有，因為有排序的話有很簡單方法就可以有解答)&#x20;
* 可能有重覆值&#x20;
* 兩個以上答案、 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&#x20;
* 換位思考。想想除了你直覺想到解法有沒有別的更好，例如 two pointer、 ，想不到的話此題是不是可以用 map 取代 Array 讓時間複雜度變低?

![](https://1787585077-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LqirD3iAZIDk4oDCfwS%2F-LqiuUZNV-jG7QBMF7Xg%2F-LqiwAPPJenaACAE0nFP%2Ftable.png?alt=media\&token=25a27d7b-1e0b-4842-a268-9b4d9e088aa5)
