【哈希】1. leetcode 1. 两数之和
1 题目描述
题目链接:两数之和
2 题目解析
一般的思维:找到两个数A和B,判断A和B相加是否为target。
我们可以采用逆向思维:找到一个数A,在nums数组中找是否有值等于target - A,因为题目要求只返回一个组合即可,因此就可以在找到之后直接return返回。
将不满足条件的都丢入哈希表中。
以前是从前往后找,现在是从后往前找。
3 代码
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> res;
unordered_map<int, int> hash;
for (int i = 0; i < nums.size(); ++ i)
{
int x = target - nums[i]; //根据nums[i],找nums中是否有值为x --> 逆向思考
if (hash.count(x))
return {hash[x], i};
//如果没有找到就建立哈希映射
hash[nums[i]] = i;
}
return {-1, -1};
}
};