【C++】1 两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

又见 twoSum，是否又进步了些？

#include <unordered_map> // 包含哈希表库
#include <vector>
#include <iostream>

using namespace std;

vector<int> twoSum(const vector<int>& nums, int target) {
    unordered_map<int, int> numMap; // 创建哈希表来存储数值及其索引

    // 遍历数组
    for (int i = 0; i < nums.size(); ++i) {
        int complement = target - nums[i]; // 计算目标值与当前数值的差值

        // 检查哈希表中是否存在这个差值
        if (numMap.find(complement) != numMap.end()) {
            // 如果存在，返回该差值的索引和当前数值的索引
            return {numMap[complement], i};
        }

        // 否则，将当前数值和它的索引添加到哈希表中
        numMap[nums[i]] = i;
    }

    // 如果没有找到符合条件的元素对，返回一个空向量
    return {};
}

int main() {
    vector<int> nums = {2, 7, 11, 15};
    int target = 9;

    vector<int> result = twoSum(nums, target);

    if (!result.empty()) {
        cout << "Indices of elements with sum " << target << ": ";
        cout << result[0] << ", " << result[1] << endl;
    } else {
        cout << "No two elements found with the given target." << endl;
    }

    return 0;
}

使用 unordered_map (哈希表) 存储已经访问过的元素及其索引。然后，通过计算目标值和当前元素的差值，检查哈希表中是否存在这个差值。如果存在，则返回对应的索引。如果不存在，将当前元素添加到哈希表中，继续下一个循环。这种方法确保每个元素最多只被访问一次，因此时间复杂度为 O(n)

在C++中，return {numMap[complement], i}; 这样的语法是使用初始化列表来创建一个std::vector（向量）对象，并直接返回该对象。这种语法也被称为列表初始化。

在这种情况下，{numMap[complement], i} 创建了一个包含两个整数的向量，分别是 numMap[complement] 和 i，它们分别代表了哈希表中目标值的索引和当前元素的索引。然后，这个向量被作为函数的返回值返回。

这种语法简洁明了，并且在返回多个值时很方便。

分析一下时间复杂度和空间复杂度

时间复杂度分析

在遍历数组时，每个元素都需要进行一些常数时间的操作，包括哈希表的插入和查找。
对于包含 n 个元素的数组，哈希表的插入和查找操作的平均时间复杂度是 O(1)。因此，整个遍历过程的时间复杂度是 O(n)。

空间复杂度分析

使用了一个哈希表来存储已经访问过的元素及其索引。
对于包含 n 个元素的数组，最坏情况下需要存储 n 个元素的索引，因此空间复杂度是 O(n)。
因此，这种方法的时间复杂度是 O(n)，空间复杂度是 O(n)。相比于暴力法的时间复杂度 O(n^2)，这种方法在效率上有明显的提升。