哈希表两数求和
leetcode题目链接
这道题思路可以说easy 首先想到的就是两层for循环
代码如下
class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {vector<int>result;int length=nums.size();for(int i=0;i<length;++i){for(int j=i+1;j<length;++j){if(nums[i]+nums[j]==target){result.push_back(i);result.push_back(j);}}}return result;}
};
但是这样写太漏了,时间复杂度太高,其实可以利用哈希表O(1)的存储复杂度来解决这道题
代码如下:
std::vector<int> twoSum(std::vector<int>& nums, int target) {std::unordered_map<int, int> num_map; // 创建哈希表for (int i = 0; i < nums.size(); ++i) {int complement = target - nums[i];// 检查哈希表中是否存在补数if (num_map.find(complement) != num_map.end()) {return {num_map[complement], i}; // 返回找到的下标}// 将当前数和下标存入哈希表num_map[nums[i]] = i;}return {}; // 如果没有找到,返回空
}
这里计算目标值与当前值的差值,如果差在哈希表中存在则找到了。
关键是知道nums_map[nums[i]]=i,这种值和键绑定的写法。