两数之和
- 难度： 简单
- 通过率： 39.7%
- 题目链接：https://leetcode-cn.com/problems/two-sum
题目描述
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
示例:
给定 nums = [2, 7, 11, 15], target = 9 因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1]
题目分析：
- 方法一：暴力解法，所有数两两组合，时间复杂度为
$O(n^2)$。 - 方法二：使用哈希表把每个数存储下来，对于
nums[i]在哈希表中查找target - nums[i]即可。
代码：
这里实现方法二，另外可以渐进地把元素插入到哈希表中。
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> mp;
for(int i=0;i<nums.size();i++){
int a = nums[i];
int b = target - a;
if(mp.find(b) != mp.end()){
return {i, mp[b]};
}else{
mp[a] = i;
}
}
return {-1, -1};
}
};