1. Two Sum

解題思路

第一時間想到的暴力解，是直接兩層迴圈去找相加和等不等於 target，時間複雜度 O(n^2)。

看提示中的 tag 有 hashTable，於是想到可以只用一次迴圈，也就是時間複雜度 O(n) 的解法。由於我們要找兩個 index，分別表示 array 中相加為 target 的兩個數，所以當我們有某個數值 n ，則需要找另一個數值 target - n 是否存在於 array。

既然這樣，那就在這一次的迴圈中，看當下這個新的數字 n，它的配對數字 target - n 是不是已經看過了(存在 map 中)。如果有，就結束這回合；如果沒有，記得把當下的數字 n 存進 map 中。

程式碼

方法一：暴力解

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> ans;
        for(int i=0; i<nums.size(); i++)
        {
            for(int j=i+1; j<nums.size(); j++)
            {
                if(nums[i] + nums[j] == target)
                {
                    ans.push_back(i);
                    ans.push_back(j);
                    return ans;
                }
            }
        }
        return ans;
    }
};

方法二：hashTable

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        map<int, int> mp;
        vector<int> ans;
        for(int i=0; i<nums.size(); i++)
        {
            if(mp.count(target - nums[i]))
            {
                ans.push_back(i);
                ans.push_back(mp[target - nums[i]]);
                return ans;
            }
            mp[nums[i]] = i;
        }
        return ans;
    }
};