twoSum

1. 两数之和

分析

利用哈希表存储数组元素及其下标：
- 使用一个哈希表，键为数组元素值，值为对应的下标
- 哈希表可以快速查询某个元素是否已经出现过
遍历数组，寻找目标值对应的数：
- 在遍历数组时，对于当前元素 nums[i]，计算另一个需要的数 x = target - nums[i]；
- 在哈希表中检查是否存在 x：
  - 如果 x 存在，说明找到了两个数，返回它们的下标
  - 如果 x 不存在，将当前数 nums[i] 及其索引存入哈希表，继续遍历

时间复杂度

哈希表查询和插入：每次操作 O(1)
数组遍历：遍历一次数组，时间复杂度为 O(n)

总时间复杂度 O(n)

空间复杂度

需要一个哈希表存储数组中的元素及其索引，空间复杂度为 O(n)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


class Solution
{
public:
    vector<int> twoSum(vector<int>& nums, int target)
    {
        std::unordered_map<int, int> hash; // 哈希表存储元素值及其索引

        for (int i = 0; i < nums.size(); ++ i)
        {
            int x = target - nums[i]; // 计算需要的数

            // 检查是否在哈希表中
            if (hash.count(x))
                return {hash[x], i}; // 找到目标值，返回下标

            // 将当前数存入哈希表
            hash[nums[i]] = i;
        }

        return {}; // 如果无解，返回空数组（题目保证一定有解）
    }
};