Two sum 題目檢討紀錄


Posted by yunanpan on 2020-07-02

LidemyOJ: Two sum 檢討

target: 3
[1, 7, 9, 8, 2]

方法一

將陣列中每個數值都兩兩相加:

1 + 7 = 8
1 + 9 = 10
1 + 8 = 9
1 + 2 = 3
7 + 9 = 11
7 + 8 = 15
7 + 2 = 9
9 + 8 = 17
9 + 2 = 11
8 + 2 = 10

會發現 1 + 2 = 3 等於 target 的值,輸出 1 及 2 的 index 便是答案。

function solve (lines) {
    let [n, target] = lines[0].split(' ').map(Number)
    let arr = lines[1].split(' ').map(Number)
    for (let i=0; i<arr.length; i++) {
        for (let j=i+1; j<arr.length; j++) {
            if (arr[i] + arr[j] === target) {
                console.log(i, j)
            }
        }
    }
}

方法二-參考解答影片與 leetcode 上的解法後修改

設定一個 object 存入陣列各數值的值與 index。
object 會長成下面這樣:

{'1': 0, '2': 4, '7': 1, '8': 3, '9': 2 }

obj 中的值大於等於 0 的話,就代表原陣列中有查詢的值。所以只要檢視 target - <陣列數值> 的值存不存在,就可以求出答案,不用再比較陣列中每個數值。
利用存取的 obj key 和 value 與 array 的 index 和相對應的值是相反的特性(例: arr[0] = 1, obj['1'] = 0),便可用 obj[target - arr[i]] 去檢視陣列中有沒有和 arr[i] 相加會等於 target 的數值存在。

function solve (lines) {
    let [n, target] = lines[0].split(' ').map(Number)
    let arr = lines[1].split(' ').map(Number)

    // 把資料存進 object 裡
    let obj = {}
    for (let i=0; i<arr.length; i++) {
        obj[arr[i]] = i
    }

    // 看 obj 裡有沒有 target - <陣列數值> 的
    for (let i=0; i<arr.length; i++) {
        if (obj[target - arr[i]] >= 0) {
            console.log(obj[arr[i]], obj[target - arr[i]])
            break
        }
    }
}

因為第二種方法不需要全部都去比對,只要取出一個數值便可直接檢查相對應的數值是否存在,所以效率高很多。










Related Posts

[Day 2] JS in Pipeline (2): Docker and Local Development Environment (2)

[Day 2] JS in Pipeline (2): Docker and Local Development Environment (2)

開啟測試這扇門的鑰匙

開啟測試這扇門的鑰匙

HHKB Studio

HHKB Studio


Comments