Leetcode题解 1.两数之和

今天得到高人指点迷津。故从今天开始刷题，先来第一题体验一下。

PROBLEM

难度简单

MY ANSWER

暴力

两个for搞定，时间复杂度O（n^2)，空间复杂度O（1）。

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

BETTER SOLUTION

哈希表

空间换时间，对于每一个 x，首先查询哈希表中是否存在 target - x，然后将 x 插入到哈希表中。

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 {};
    }
};

时间复杂度O（n)，空间复杂度O（n）。

SUMMARY

热手题目，太久没写，哈希表都没想出来。牢记：空间换时间，查询可以通过哈希表来降低复杂度，解题时多注意数据结构的设计。另外发现自己对STL了解不多，得多学习熟悉一下加快打码速度，毕竟写了快两年C，CPP快忘光了。