【C++刷题】力扣-#1-两数之和

问题描述

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案，但是数组中同一个元素不能使用两遍。

算法设计

我们可以使用哈希表来存储数组元素及其索引，这样我们就可以在 O(1) 时间内查找目标值与当前元素的差值是否已经在哈希表中出现过。

1. 初始化一个空的 map，用于存储数组元素及其索引。
2. 遍历数组中的每个元素：
   ○ 计算目标值与当前元素的差值。
   ○ 检查这个差值是否已经在哈希表中存在：
   ■ 如果存在，说明我们找到了一对和为目标值的元素，返回它们的索引。
   ■ 如果不存在，将当前元素及其索引存入哈希表中。
3. 如果遍历结束后没有找到符合条件的元素对，返回一个空的 vector。

代码实现

vector<int> twoSum(std::vector<int>& nums, int target) {map<int, int> indexMap;for (int i = 0; i < nums.size(); i++) {int complement = target - nums[i];if (indexMap.find(complement) != indexMap.end()) {return {indexMap[complement], i};}indexMap[nums[i]] = i;}return {}; // 返回一个空的 vector 表示没有找到解
}

复杂度分析

● 时间复杂度：O(n)，其中 n 是数组 nums 的长度。我们只需要遍历一次数组。
● 空间复杂度：O(n)，因为我们需要存储所有元素的索引到哈希表中。
这个算法的优势在于它的时间效率较高，只需要遍历一次数组。使用哈希表可以在平均情况下快速查找元素，使得算法的效率大大提升。