复习Day08：哈希表part01:242.有效的字母异位词、349. 两个数组的交集、1. 两数之和、160. 相交链表

之前的blog：https://blog.csdn.net/weixin_43303286/article/details/131765317

我用的方法是在leetcode再过一遍例题，明显会的就复制粘贴，之前没写出来就重写，然后从拓展题目中找题目来写。辅以Labuladong的文章看。然后刷题不用CLion了，使用leetcode自带模拟面试环境。

哈希表章节的题目思路很清晰，主要是C++中的写法。

242.有效的字母异位词

这题就是字典加加减减的事，一看就有思路了。使用数组代替hashtable

349. 两个数组的交集

这里注意在C++的std::unordered_set中，查找一个元素的平均时间复杂度是O(1)。这是因为unordered_set是使用哈希表实现的，哈希表提供了常数时间的平均查找时间，前提是哈希函数能够将元素均匀地分布在哈希表的桶中，并且没有发生哈希冲突。

在C++的std::unordered_set中，你可以使用find函数来查找元素。find函数返回一个迭代器，指向找到的元素，如果元素不存在，则返回unordered_set的end()迭代器。

在C++的std::unordered_set中插入元素可以使用insert函数

我的第一个解法使用两个set：

class Solution {
public:vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {unordered_set<int> sets(nums1.begin(), nums1.end());unordered_set<int> res;for(int num: nums2){if(sets.find(num) != sets.end()){res.insert(num);}}return vector<int> (res.begin(), res.end());}
};

内存爆了，看看之前的解法：感觉这个时间复杂度更差hhh

class Solution {
public:vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {unordered_map<int,int> table;set<int> res;for(int num : nums1){table[num]++;}for(int num : nums2){if(table[num] > 0){res.insert(num);}}vector<int> res1(res.begin(),res.end());//使用迭代器构建vector。return res1;}

1. 两数之和

使用hashtable，其中key是值，value是对应的下标

这里注意使用iter取hash表中的迭代器，it->second表示value，没有括号。

160. 相交链表

二刷有点思路了，先遍历一遍求长度，然后移动短的跟长的对齐，再依次比较相等就返回（这里比的不是值而是指针）：

class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {ListNode* curA = headA;ListNode* curB = headB;int lengthA = 0, lengthB = 0;while(curA != nullptr){lengthA++;curA = curA->next;}while(curB != nullptr){lengthB++;curB = curB->next;}//这里要重新开始遍历，要对curA curB进行重新赋值curA = headA;curB = headB;//假设A为短的链表，B为长的链表if(lengthA > lengthB){swap(lengthA,lengthB);swap(curA,curB);}int gap = lengthB - lengthA;while(gap--){curB = curB->next;}while(curA != nullptr){if(curA == curB){return curA;}curA = curA->next;curB = curB->next;}return nullptr;}
};
z