C++20 实现 两数之和：哈希表解法

C++20 实现 两数之和：哈希表解法

题目描述：

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

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

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

题目分析：

题目要求在一个整数数组中找出两个数的和为目标值，且这两个数的下标不能重复。我们可以使用哈希表来解决这个问题。哈希表可以将数组中的数与对应的下标存储起来，然后遍历数组，对于每个数，在哈希表中查找是否存在一个数与它的和为目标值，如果存在，则找到了答案。时间复杂度为O(n)。

代码实现：

#include <unordered_map>
#include <vector>

class Solution {
public:
    std::vector<int> twoSum(std::vector<int>& nums, int target) {
        std::unordered_map<int, int> hash_map;
        for (int i = 0; i < nums.size(); i++) {
            int complement = target - nums[i];
            if (hash_map.count(complement)) {
                return {hash_map[complement], i};
            }
            hash_map[nums[i]] = i;
        }
        return {};
    }
};

代码解释：

1. 使用 std::unordered_map 作为哈希表，键为数组中的数，值为对应下标。
2. 遍历数组，对于每个数 nums[i]，计算其与目标值的差值 complement。
3. 在哈希表中查找是否存在 complement，如果存在，则找到了答案，返回 complement 对应的下标和当前下标 i。
4. 如果不存在 complement，则将当前数 nums[i] 和其下标 i 存入哈希表。
5. 如果遍历完整个数组都没有找到答案，则返回空向量 {}。

总结：

本文使用 C++20 中的 std::unordered_map 实现了两数之和问题，通过哈希表存储数组中的数及其下标，能够在 O(n) 的时间复杂度内找到答案。这种解法简洁高效，易于理解和实现。