两数之和
题目描述
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那两个整数，并返回它们的数组下标。题目链接
你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。
你可以按任意顺序返回答案。
示例 1
输入：nums = [2,7,11,15], target = 9 输出：[0,1] 解释：因为 nums[0] + nums[1] == 9，返回 [0, 1]。
示例 2
输入：nums = [3,2,4], target = 6 输出：[1,2]
示例 3
输入：nums = [3,3], target = 6 输出：[0,1]
解题思路
暴力枚举法 首先想到的方法就是直接暴力枚举，让两数之和等于 target 即可，这样的话时间复杂度就是
O
(
N
2
)
O(N^2)
O(N2)。
哈希表优化法（最优解） 最优的方法是将 nums 存入哈希表中，然后遍历数组的时候直接查找哈希表中是否有 target-nums[i] 的值即可。
- 哈希表查找的时间复杂度为
O
(
1
)
O(1)
O(1) - 整体时间复杂度降到了
O
(
N
)
O(N)
O(N) - 空间复杂度：需要额外的空间
O
(
N
)
O(N)
O(N) 来存储哈希表
代码优化点： 写代码的时候不需要先预处理哈希表，直接在遍历的过程中将当前无法匹配的值存入哈希表即可（如果当前值的匹配值还在后面，这样当遍历到匹配值的时候，当前值已经在哈希表中了，依旧可以匹配）。 需要注意：键是 nums[i]，值是下标 i，因为我们需要返回的的匹配值的下标。
C++ 代码实现
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int,int> hash;
for (int i = 0; i < nums.size(); i++) {
// 查找是否存在目标差值
if (hash.find(target – nums[i]) != hash.end()){
return {i, hash[target – nums[i]]};
}
// 不存在则将当前元素存入哈希表
hash[nums[i]] = i;
}
// 题目保证有解，此处仅为语法完整性
return {};
}
};
每日心灵鸡汤
知不足，而奋进。
