复习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());
        
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

内存爆了，看看之前的解法：感觉这个时间复杂度更差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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38