Two sum 題目檢討紀錄

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

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