【LeetCode】两数之和

1.两数之和

1.My solution

class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
    vector<int> s;
    int n = nums.size();
    if (n == 0) return s;
    set<int> inter;
    for (int i = 0; i < n; i++)
    {
       inter.insert(nums[i]);
    }
    for (int i = 0; i < n; i++)
    {
        int temp = target - nums[i];
        if (!inter.count(temp)) continue;
        for (int j = n - 1; j > i; j--)
        {
            if (nums[j] == temp)
            {
                s.push_back(i);
                s.push_back(j);
                return s;
            }
        }
    }
    return s;
}
};

2.Official solution

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

3.summary

1. 官方使用的向前回溯，而我使用的向后回溯，需要提前把数据都存好，浪费空间。
2. 官方利用巧妙地利用了键值与find
3. 学习set与unordered_map的使用