C++算法练习-day15——1.两数之和
题目来源：. - 力扣（LeetCode）
题目思路分析
题目描述：
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
思路分析：
-
暴力解法：最直接的方法是使用两层循环遍历数组，对于每一对元素，检查它们的和是否等于目标值。这种方法的时间复杂度为 O(n^2)，在数组较大时效率较低。
-
哈希表优化：我们可以利用哈希表（在C++中通常使用
unordered_map）来存储数组中的元素及其对应的索引。这样，在遍历数组时，我们可以直接检查target - nums[i]是否已经在哈希表中，如果存在，则找到了答案。这种方法的时间复杂度为 O(n)，因为每个元素只被遍历一次，哈希表的查找操作平均时间复杂度为 O(1)。
代码：
#include <vector>
#include <unordered_map>
using namespace std;
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
// 创建一个哈希表来存储数组元素及其索引
unordered_map<int,int> hashtable;
int n = nums.size(); // 获取数组长度
// 遍历数组
for(int i = 0; i < n; ++i){
// 计算当前元素需要的配对值
int complement = target - nums[i];
// 在哈希表中查找配对值
auto it = hashtable.find(complement);
// 如果找到了配对值，则返回它们的索引
if(it != hashtable.end()){
return {it->second, i};
}
// 如果没找到，则将当前元素及其索引存入哈希表
hashtable[nums[i]] = i;
}
// 如果没有找到任何配对，返回一个空数组
return {};
}
};注释详解
unordered_map<int,int> hashtable;：创建一个哈希表，键为数组中的元素值，值为该元素在数组中的索引。int n = nums.size();：获取数组的长度。for(int i = 0; i < n; ++i)：遍历数组。int complement = target - nums[i];：计算当前元素需要的配对值，即目标值减去当前元素的值。auto it = hashtable.find(complement);：在哈希表中查找配对值。if(it != hashtable.end())：如果找到了配对值，说明之前已经遍历过一个元素，它的值与当前元素的配对值相等。return {it->second, i};：返回之前元素的索引和当前元素的索引。hashtable[nums[i]] = i;：如果没找到配对值，则将当前元素及其索引存入哈希表。return {};：如果遍历完数组后没有找到任何配对，返回一个空数组。
知识点摘要
- 哈希表（unordered_map）：一种高效的键值对存储结构，支持快速的查找、插入和删除操作。
- 时间复杂度：哈希表的查找、插入和删除操作平均时间复杂度为 O(1)。
- 数组遍历：使用循环遍历数组的每个元素。
本文介绍了一种使用哈希表解决“两数之和”问题的高效方法。通过遍历数组并使用哈希表存储已经遍历过的元素及其索引，我们可以在 O(n) 的时间复杂度内找到和为目标值的两个整数及其索引。这种方法不仅提高了效率，而且代码简洁易懂，是处理此类问题的推荐方法。希望这篇文章能帮助你更好地理解并掌握这一算法技巧。