Leetcode 1 - Two Sum

題目

Problem#

題目給你一個整數陣列 nums 和一個正數 target，問你哪兩個數字加起來等於 target。
每組輸入一定都會有解，回傳 index 即可。

想法#

$\mathcal{O}(N^2)$ 的解很簡單，直接做就好。$\mathcal{O}(N\log{N})$的解，先記錄數字對應到的位置(同個數字可能出現在多個位置)，接著遍歷每個數字 i，看看 target - n[i] 有沒有在裏頭，如果有且沒挑過的話，則找到答案

• 時間複雜度: $\mathcal{O}(N\log{N})$
• 空間複雜度: $\mathcal{O}(N)$

AC Code#

賞析#

• 用 dictionary 紀錄數值對應到位置映射，邊建邊找解答
  • https://leetcode.com/problems/two-sum/discuss/13/Accepted-C%2B%2B-O(n)-Solution

linenums

vector<int> twoSum(vector<int>& n, int t) {
    unordered_map<int, int> M;
    
    for (int i = 0;; ++i) {
        auto it = M.find(t - n[i]);
        
        if (it != M.end()) 
            return vector<int> {i, it->second};
            
        M[n[i]] = i;
    }
}

心得#

經典的第一題，看了題解才覺得我的解法好像太複雜了