runtime 4 ms, beats 99.47% of cpp submissions
O(n) solution with explanation

tags: hashmap

two sum

📖 description

給予一個陣列 nums ，在其中找到兩個數字的總合為 target ，並回傳所在的 index

🧠 solution

在遍歷陣列的同時將目前看到的 nums[i] 紀錄在 unordered_map 中，並觀察 target - nums[i] 是否存在 map 裡

⏳ time complexity

遍歷一次 O(n) ， unordered_map 的每次操作均攤為 O(1) 共 n 次操作
總時間複雜度 O(n)

📝 code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int t) {
        unordered_map<int,int> map;
        int m=nums.size();
        for(int i=0;i<m;i++){
            if(map.find(t-nums[i])!=map.end()){ // 找 t-nums[i] 是否存在 map 中
                return {map[t-nums[i]],i};
            }
            map[nums[i]]=i; //紀錄看過的數字
        }
        return {-1,-1};
    }
};