仅以此记录所学所想,如有错误,还望指正。
1. 代码块
class Solution{public:vector<int> twoSum(vector<int>& nums, int target) {//建立哈希表,int1:key=元素值,int2:value=元素索引,因为我们要通过元素值来查找,所以把它作为key,元素索引作为valueunordered_map<int,int>hashtable;for(int i=0;i<nums.size();i++){int complement=target-nums[i];//如果可以找到这个值,则返回两个值的索引auto it=hash.find(complement);if(it!=hash.end()) return {it->second,i};//如果没有找到,则将当前值和索引存入哈希表hash[nums[i]]=i;}return {};}
}
2. 简单理解
-使用哈希表,时间复杂度为O(n),如果暴力解题,时间复杂度为O(n^2)。
但我感觉理解起来差不多,暴力是向后查找complement,用for循环遍历数组,O(n);哈希表是向前查找(前面的值已经以键值对的形式存进表内),O(1)。
3.哈希表
(刚开始束手无措是因为之前没认真学哈希表,在这里简单写一下就当复习了。)
3.1 核心容器
unordered_map 存储键值对
unordered_set 仅存储键
键不可重复,值可以重复
3.2 基本操作
1、插入:hashtable[key] = value
2、查找:
auto it=hash.find(key);
if(it!=hash.end())
{cout<<it->second<<endl;// it->first是key,it->second是value
}
else {cout<<not found<<endl;}
3、删除:
1、通过键删除: hash.erase(key)
2、通过迭代器删除
auto it=hash.find(key); if(it!=hash.end()) hash.erase(it);
4、遍历:for(auto it=hash.begin();it!=hash.end();it++)
5、大小:hash.size()
6、清空:hash.clear()
7、判空:hash.empty()
8、是否存在某个键:hash.count(key)
注意:哈希表的插入、查找、删除操作的时间复杂度都是O(1)