[LeetCode筆記]#1 — Two Sum(Easy)

題目

輸入一個vector(nums)以及整數(target)
回傳兩個數相加等於target的indices

限制條件：
2 ≤ nums.length ≤ 10³
-10⁹ ≤ nums[i] ≤ 10⁹
-10⁹ ≤ target ≤ 10⁹
必存在一解

Example:
Input : nums = [2, 7, 11, 15 ], target = 9
Output : [ 0, 1 ]

想法

一開始我是利用vector去存取遍歷過的數
但vector在查找上遜於unordered_map
unordered_map查找的時間複雜度為 O(1)
故此題採用unordered_map來存放遍歷過的數
讓時間複雜度能達到O(n)。

演算法

遍歷vector中的數，若為target減掉當前的數，則回傳此兩數的indices
若不是，則將當前的數放入unordered_map。