[Easy] 1. Two Sum
本文共 1223 字，大约阅读时间需要 4 分钟。
解决方案：使用哈希表来优化查找过程，时间复杂度为O(n)
问题描述
给定一个整数数组，找到两个数的索引，使得它们的和等于一个特定的目标值。每个输入都有一个唯一的解，且不能使用同一个元素两次。
解决方法
为了高效地解决这个问题，我们可以使用哈希表（字典）来优化查找过程。哈希表允许我们在常数时间内查找特定值，这将使得整体时间复杂度降低到O(n)，其中n是数组的长度。
方法思路
问题分析：
- 我们需要找到两个数，使得它们的和等于目标值。
- 每个输入都有一个唯一的解，确保我们能找到正确的配对。
哈希表的使用：
- 创建一个哈希表，键是数组中的数值，值是对应的索引。
- 遍历数组中的每个元素，计算一个关键码
key = target - nums[i]。 - 检查哈希表中是否存在这个关键码：
- 如果存在，说明已经找到了配对的数，返回当前索引和哈希表中的值。
- 如果不存在，将当前数值和索引存入哈希表，继续处理下一个元素。
代码实现
#include #include using namespace std;class Solution {public: vector twoSum(vector nums, int target) { unordered_map hmap; for (int i = 0; i < nums.size(); ++i) { int input = nums[i]; int key = target - input; if (hmap.find(key) != hmap.end()) { return {hmap[key], i}; } hmap[input] = i; } return {}; }};
代码解释
- 初始化哈希表：
unordered_map<int, int> hmap; 用于存储数值及其对应的索引。 - 遍历数组：
for (int i = 0; i < nums.size(); ++i) 遍历每个元素。 - 计算关键码：
int key = target - nums[i]; 计算目标减去当前元素的值。 - 查找关键码：
if (hmap.find(key) != hmap.end()) 检查哈希表中是否存在该关键码。 - 找到配对：如果存在，返回哈希表中对应的值和当前索引。
- 存入哈希表：如果不存在，将当前数值及其索引存入哈希表。
- 返回结果：一旦找到配对，立即返回结果，减少不必要的计算。
这种方法确保了在最佳时间复杂度内解决问题，适用于大规模数据。
转载地址：http://dyir.baihongyu.com/