两数之和
给定整数数组 nums 与目标值 target，找出数组中相加等于 target 的两个数，返回它们的下标，保证仅有一组解，不可复用同一元素，下标返回顺序不限。
LeetCode1分钟阅读
![在数组 nums = [4, 2, 11, 7] 中，目标值为 9。指针 $p1$ 和 $p2$ 分别定位到数字 2（下标 1）和 7（下标 3），因 $2 + 7 = 9$，故最终返回下标组合 [1, 3]](/_astro/twoSum.B4Oowpzz_G2VIA.webp)
给定一个整数数组
nums和一个整数目标值target，请你在该数组中找出 和为目标值target的那 两个 整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。
你可以按任意顺序返回答案。
示例 1：
示例 2：
示例 3：
提示：
2 <= nums.length <= 104-109 <= nums[i] <= 109-109 <= target <= 109- 只会存在一个有效答案
双重循环枚举所有可能性。对于每个数 x，遍历剩下的元素查找是否有 target - x。效率较低。
遍历数组时，我们需要知道“之前是否见过满足条件的另一个数”。利用哈希映射（Map）建立 数值 -> 数组下标 的映射关系：
- 遍历当前数字
nums[i]。 - 计算目标补数
complement = target - nums[i]。 - 检查哈希表中是否存在
complement：- 存在： 说明找到了匹配对，直接返回
[哈希表记录的下标, i]。 - 不存在： 将当前的
nums[i]及对应下标i存入哈希表，继续遍历。
- 存在： 说明找到了匹配对，直接返回
class Solution {public: vector<int> twoSum(vector<int>& nums, int target) { // 哈希表：用于存储【数值 -> 数组下标】的映射 // 这样可以将查找补数的时间复杂度降为 O(1) unordered_map<int, int> hashtable;
// 遍历数组中的每一个元素 for (int i = 0; i < nums.size(); ++i) { // 计算当前数字所需的补数 (target - 当前值) int complement = target - nums[i];
// 在哈希表中查找是否已经存在这个补数 auto it = hashtable.find(complement);
// 如果找到了匹配的补数 if (it != hashtable.end()) { // it->second 是之前存入的补数的下标，i 是当前元素的下标 return {it->second, i}; }
// 如果没找到，将当前【数值 : 下标】存入哈希表，供后续元素查找 hashtable[nums[i]] = i; }
// 如果遍历结束仍没有找到符合条件的解（按题目逻辑通常不会执行到这里） return {}; }};- 时间复杂度： ，只需遍历一次数组，哈希表插入与查找的时间复杂度为 。
- 空间复杂度： ，哈希表最多需要存储 个元素。