LeetCode 1. Two Sum [Easy] [C++] 解題筆記

LeetCode 第一題一定要寫一下拉，這題給定一個 array 與一個 target value 要求我們從 array 中找到兩個數字和為 target，並保證一定且唯一存在一個解 。

EX:

        nums = [2, 7, 11, 15], target = 9

        Ans: [0, 1] , nums[0] + nums[1] = 9

想法:

        這題除了暴力兩兩數字之和以外，我們可以用一個 HashMap 儲存出現過的數字，然後在遍歷整個 array 時尋找 HashMap 中是否有 target - nums[i] 即可求解。

Complexity: O(n) time, O(n) space.

完整程式碼:

class Solution {

public:

    vector<int> twoSum(vector<int>& nums, int target) {

        // unordered_map find take O(1) in average

        unordered_map<int, int> m;

            

        for (int i = 0; i < nums.size(); i++) {

            if (m.find(target - nums[i]) != m.end()) {

                return {i, m[target - nums[i]]};

            }   

            m[nums[i]] = i;

        }   

            

        return {}; 

    }   

};