題目網址：https://leetcode.cn/problems/two-sum/

題意：給一 array nums 和一整數 target, 求 nums 中兩數和剛好為 target 之 index, 假設每一種 target 只會對應到一組解。

注意：同一個元素不可重複使用, 可按照任意順序返回。

Solution：

想法：利用 hash table, 由於題目保證一定有解, 因此對 nums[i] 而言, 先去 hash table 中找 target - nums[i] 是否存在

  • 若存在, 則直接返回
  • 否則, 將 nums[i] 還有其 index 加入到 hash table 中
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> umap;  // {value, index}
        for (int i = 0; i < nums.size(); i++) {
            const int search = target - nums[i];
            if (umap.find(search) != umap.end()) {
                return {i, umap[search]};
            }
            umap[nums[i]] = i;
        }
        return {};
    }
};
  • time：$O(n)$ ➔ 遍歷 nums
  • space：$O(n)$ ➔ umap 的元素個數不超過 n