leetcode1两数之和

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

时间复杂度为 O(n)，其中 n 是输入向量 nums 的长度。具体分析如下：

创建一个 unordered_map 哈希表，时间复杂度为 O(1)。

遍历 nums 向量，对于每个元素 nums[i]，在哈希表中查找是否存在 target – nums[i] 的元素，时间复杂度为 O(1)，因为哈希表的查找时间是常数级别的。

如果哈希表中存在 target – nums[i] 的元素，直接返回两个元素的下标，时间复杂度为 O(1)。

如果哈希表中不存在 target – nums[i] 的元素，将当前元素插入到哈希表中，时间复杂度为 O(1)。

因此，总的时间复杂度为 O(n)，并且由于本算法只使用了一个 unordered_map 哈希表来存储数据，因此空间复杂度也为 O(n)。

执行用时：12 ms, 在所有 C++ 提交中击败了67.72%的用户

内存消耗：10.7 MB, 在所有 C++ 提交中击败了21.00%的用户