難度: Easy
類型: Array, Hash Table
==========================
Hash Table 的題目, LeetCode 的第一題, 與某一線外商的 coding interview 的介紹影片題目相近。
==========================
前情題要:
簡單說就是找到兩個 nums verctor<int> 中的index, 他們對應的值相加等於 target
==========================
思考方式與複雜度:
1. 一樣從簡單直覺開始, 就兩個數字, 第一個數字的 index i從 0~nums_size; 另一個數字的 index j 從 i+1~nums_size; 找到兩個相加等於 target 就回傳 {i,j}。這樣的 time O(N^2), 但由於不需要多餘的memory complexity O(1)
2. 另一個比較快的方式, 用 unordered_map, 因為題目有寫唯一解, 所以就不必用到 multimap。每一個 nums 的element值, 都檢查有沒有它的 complement 值在 unordered_map 裡, 有的話就是找到答案, 把該 index 和在 unordered_map 裡的 index 組起來回傳答案。如果沒找到, 就把這個值的 complement 當作 key, index當作value, 存進 unordered_map 中, 如果最後一個 element 都找不到 complement, 就回傳空集合{}, 同時記得debug, 因為題目說有唯一解。這個時間複雜度O(N), 空間複雜度也是O(N)。
=======================
結果:
Accepted 63 / 63 testcases passed
1. 第一種方法
Runtime: 34 ms, Beats: 41.30%
Memory: 13.99 MB, Beats: 92.87%
2. 第二種方法
Runtime: 0 ms, Beats: 100%
Memory: 14.73 MB, Beats: 50.22%
