LeetCode - 1. 两数之和

题目

1. 两数之和 - 力扣（LeetCode）

思路

这是一道经典的算法题，我的思路是用哈希表来解决，可以将时间复杂度优化到O(n)。

首先，我会遍历数组，对于每个元素，计算它与目标值的差值。然后检查这个差值是否已经在哈希表中。如果在，就找到了答案；如果不在，就把当前元素及其索引存入哈希表。

具体实现时，我会用一个无序哈希表，键是数组元素值，值是索引。

读者可能出现的问题

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {unordered_map<int,int> hash; for(int i =0;i<nums.size();i++){hash[nums[i]]++;}for(int i = 0;i<nums.size();i++){if(hash.count(target - hash[nums[i]])){return {i,target - hash[nums[i]]};}}return {0,0};}
};

unordered_map<int, int> hash;: 你用unordered_map存储的是每个数字的出现次数，而在做target - hash[nums[i]]时，你实际上在查找的是某个数字的数量，这并不是你想要的。你应该存储的是数字和它们的索引，而不是次数。
if (hash.count(target - hash[nums[i]])): 这里，你在比较target - hash[nums[i]]，但你希望的是判断target - nums[i]是否存在于hash中。因此，条件判断的表达式是错误的。
你希望返回的是两个数的索引，而不是数字的值，因此返回的结果应该是索引，而不是目标数值。

正确的写法

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {unordered_map<int,int> hash; for(int i =0;i<nums.size();i++){int x = target - nums[i];if(hash.count(x)){return {i,hash[x]};}hash[nums[i]] = i;}return {-1,-1};}
};