leetcode-哈希表

1. 理论

从哈希表的概念、哈希碰撞、哈希表的三种实现方式进行学习

哈希表：用来快速判断一个元素是否出现集合里。也就是查值就能快速判断，O（1）复杂度；

哈希碰撞：拉链法，线性探测法等。只是一种思想，刷题我们自己是无需实现的，只是使用；

哈希表的三种实现方式：数组，set（集合），map（映射）。其中集合和映射分别又有三种实现。

2. 做题的时候用到的小tip：

1. set和vector不能直接相互转换，但可以通过遍历一个容器并将其元素插入另一个容器实现数据转换。

以下是将 std::set 转换为 std::vector 和将 std::vector 转换为 std::set 的示例：

将 std::set 转换为 std::vector：std::vector<int> myVector(mySet.begin(), mySet.end());

将 std::vector 转换为 std::set：std::set<int> mySet(myVector.begin(), myVector.end());

如果不是定义，直接return的时候，就用return set<int>(myVector.begin(), myVector.end()); 就行。

3. 有效的字母异位词

本题用数组就能完成，但是用到的是哈希思想。

class Solution {
public:bool isAnagram(string s, string t) {if(s.length()!=t.length())return false;int hash[26] = {0};for(char i : s){hash[i-'a']++;}for(char i : t){hash[i-'a']--;}for(int i : hash){if(i != 0)  return false; }return true;}
};

4. 两个数组的交集Leetcode349. 20230904 set操作、转换、哈希思想

如果使用unordered_set(底层为哈希表)，代码如下：

class Solution {
public:vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {unordered_set<int>result_nums;// 最终返回的交集unordered_set<int>tmp_nums(nums1.begin(), nums1.end());// 用于比较的集合        for(int i : nums2){if(tmp_nums.find(i) != tmp_nums.end()){result_nums.insert(i);}}return vector<int>(result_nums.begin(),result_nums.end()); }
};

写这一题的时候由于不熟悉set和vector之间的相互转换，卡了好久。思路倒是不难，但是要声明两个unordered_set。先是用第一个uset存nums1的所有值，然后比较nums2是否在uset里，如果在，就加入到第二个uset中去。

所以为什么要用一个uset存，而不是直接用nums2与vector的nums1比呢？这就是本题的哈希所在，因为对于unordered_set查找只需O(1时间，如果直接将nums2与nums1的vector比较，那么每次查找操作的平均时间复杂度将是O(n)，因为在vector中查找元素需要遍历整个vector，而不是像unordered_set一样具有O(1)的查找时间。这会导致整个算法的时间复杂度更高。

这种做法的主要优势在于查找的时间复杂度更低，使得整个算法的性能更好。

如果使用数组，也是类似的：

class Solution {
public:vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {unordered_set<int> result;int tmp[1000]={0};for (int i : nums1){tmp[i] = 1;}for (int j : nums2){if(tmp[j] == 1)result.insert(j);}return vector<int>(result.begin(),result.end());}
};

先用tmp 01数组存nums1中出现过的值，然后遍历nums2看tmp数组对应有没有变过，变过则插入uset。

然后我又做了一个不去重的交集题，麻烦的是有个限制条件让我们次数不一致取最小值，就要使用find之后erase iterator而不能直接用erase。这个也是我上网查了之后才知道的。

class Solution {

public:

    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {

        // 不去重，考虑使用multiset

        multiset<int> result;

        multiset<int> tmp(nums1.begin(),nums1.end());

        for(int i : nums2){

            auto it = tmp.find(i);

            if(it != tmp.end()){

                result.insert(i);

                tmp.erase(it);

            }

        }

        return vector<int>(result.begin(),result.end());

    }

};

这个我没检查就提交一次过了，晕晕

5. 快乐数 LeetCode. 202 20230905

这一题居然不是数学是哈希 还真是没想到。并且，这一题对于各位数取平方再相加的操作是我要学习的，当时写的时候觉得很头大，没想到包装成一个函数之后还是很容易的。

class Solution {
public:int calculatesum(int n){int sum = 0;while (n){sum += (n % 10) * (n % 10);n /= 10;}return sum;}bool isHappy(int n) {// 计算平方,填入哈希表并比较unordered_set<int> myset;int sum = n;while(sum != 1){sum = calculatesum(sum);if(myset.find(sum) != myset.end()){return false;}   else{myset.insert(sum);} }return true;}
};

6.两数之和 LeetCode 1. 20230905

老生常谈的题，但是每次做都有不一样的感受。前年只会暴力解，去年仅知道可以用unordered_map，今年的进步在于读懂了题目为什么这样出，限制不重复就是为了我们用unorder_map，限制时间复杂度其实就是提示unordered的查询和插入效率均为O（1）。

还有一个就是

iter->second     ,不带括号  

和return {a,b}; 这个用法不能忘掉。开始写的小括号，又换成中括号。

还有pair操作，是insert((pair)<int,int>(a,b))

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {unordered_map<int,int> mymap;int size = nums.size();for(int i = 0; i < size; ++i){auto it =  mymap.find(target - nums[i]);if( it != mymap.end()){return {i, it->second};}else{mymap.insert(pair<int,int>(nums[i],i));}}return {-1,-1};}
};

思想是遍历vector,用unordered_map存放之前遍历过的元素集合和它们对应的序号，每遍历到一个元素，在遍历过的集合里找是否有target减它的元素。

7.四数相加 II LeetCode 454. 20230908

思想是两个数组一起。前两个数组用于填充，后两个数组用于查询，跟之前一样。

需要注意的是可以可以直接使用umap[i]++这种操作。

class Solution {
public:int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {unordered_map<int,int> umap;int count = 0;for(int i : nums1){for(int j : nums2){umap[i+j]++;}}for(int i : nums3){for(int j : nums4){auto it = umap.find(-i-j);if(it != umap.end()){count += it->second;}}}return count;}
};

如果本题想难度升级：就是给出一个数组（而不是四个数组），在这里找出四个元素相加等于0，答案中不可以包含重复的四元组。

8.赎金信 LeetCode383. 20230908

class Solution {
public:bool canConstruct(string ransomNote, string magazine) {int character[26]={0};for(char i : magazine){character[i-'a']++;}for(char i : ransomNote){character[i-'a']--;if(character[i-'a'] < 0)return 0;}return 1;}
};

现在看到简单题基本就是嘎嘎乱杀了，这一题完全无难度，三分钟秒掉。

有一点需要注意：数组需要初始化……TAT

9. 三数之和

这一题的数据就是一个数组，我还以为跟之前一样，是三个数组。

这一题不建议用哈希法，因为是“去重”的，建议的方法是排序+双指针+去重。

去重是三个地方，我写的代码还跟随想录不一样，先以自己的为主。

遇到了一个坑：i++和continue，应该写continue，因为-4，-2，-2，-2，0,1,2,2,2,3,3,4,4,6,6

这个里面，i如果到了第二个-2，会直接+1，然后到了第三个-2又能够顺利往下运行，然后又会找到和第二个-2相同的三元组。想了好久的。

正确的做法应该是第二个-2：跳过！

第三个-2：跳过！

这样就能到0。

贴一个我自己写出来的代码：

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {vector<vector<int>> result;sort(nums.begin(),nums.end());for(int i = 0; i < nums.size(); ++i){if(nums[i] > 0)return result;if(i > 0 && nums[i] == nums[i - 1]){continue;}for(int left = i + 1, right = nums.size() - 1; left < right; ){if(nums[left] + nums[right] + nums[i] > 0){right--; }else if(nums[left] + nums[right] + nums[i] < 0){left++;}else {result.push_back({nums[i], nums[left], nums[right]}); //找到了一个答案left++;right--;while(left < right && nums[left] == nums[left - 1]) left++;//去重while(left < right && nums[right] == nums[right + 1]) right--;//去重}}}return result;}
};

10.四数之和

第一次提交通过了239/293个用例。但是，就这一行写了两个bug

①一开始写的不是j>1，复制了i>0过来，写的是if(i>0&&nums[j]==nums[j-1])，通过239/293

②后来写成图上的if(j>1&&nums[j]==nums[j-1])完全没考虑i==j的情况，于是改成if(j>i+1&&nums[j]==nums[j-1])，结果通过284/293……服了，然后改成longlong，结果因为中间结果是用int存的，还是不行

③然后把代码改成了这个丑陋的样子，终于过了，用时一个小时，啥也不想说了