1. Two Sum

1.問題

• 給予一個整數的array, 回傳兩個數值的索引其相加的總和為指定的目標

• 你可以假設每個input只有一組答案, 而且不會使用到相同的元素兩次

2.想法

• 第一種想法是使用recursive + back tracking, 但是這會很花時間, 太多操作

• 第二種只需要花費O(N)的時間, 將數字儲存到unorder_map中 (map的key是數值, value是索引), 並一邊在map中尋找target - 數值, 如果找到了就則把map的value, value都放到要回傳的vector中

3.程式碼

• 第一種方法

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> res;
        vector<int> records;
        vector<bool> used(nums.size(), false);
        tryGetSum(nums, res, records, used, target, 0);
        return res;
    }
private:
    void tryGetSum(vector<int>& nums, vector<int>& res, vector<int>& records, vector<bool>& used, int target, int start) {
        if (records.size() == 2 && 
            (nums[records[0]] + nums[records[1]]) == target){
            res.push_back(records[0]);
            res.push_back(records[1]);
            used[records[0]] = true;
            used[records[1]] = true;
            return;
        } else if (records.size() == 2 && (nums[records[0]] + nums[records[1]]) != target){
            return;
        }
        for (int i = start; i < nums.size(); i++) {
            if (!used[i]) {
                used[i] = true;
                records.push_back(i);
                tryGetSum(nums, res, records, used, target, i + 1);
                records.pop_back();
                used[i] = false;
            }
        }
    }
};

• 第二種方法

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> hash;
        vector<int> v;
        for(int i = 0; i < nums.size(); i++) {
            int search = target - nums[i];
            if (hash.find(search) != hash.end()) {
                v.push_back(hash[search]);
                v.push_back(i);
                return v;
            }
            hash[nums[i]] = i;
        }
        return v;
    }
};

4.Performance

• 第一種方法

• 第二種方法