复习Day09：哈希表part02:141.环形链表、142. 环形链表II、454.四数相加II、383赎金信

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

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

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

141. 环形链表

这题只需要判断是否成环，快指针走两步慢指针走一步看看最后会不会相遇。

class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode* fast = head, *slow = head;
        while(fast != nullptr && fast->next != nullptr){
            fast = fast->next->next;
            slow = slow->next;
            if(fast == slow){
                return true;
            }
        }
        return false;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

142. 环形链表II

这题不仅需要判断是否成环，还要判断环的入口，方法还是一样，但在快指针到头后，慢指针重新走找到环入口：

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode* fast = head;
        ListNode* slow = head;
        while (fast != nullptr && fast->next != nullptr) {
            fast = fast->next->next;
            slow = slow->next;
            if (fast == slow) break;

        }
        // 上面的代码类似 hasCycle 函数
        if (fast == nullptr || fast->next == nullptr) {
            // fast 遇到空指针说明没有环
            return nullptr;
        }
         // 重新指向头结点
        slow = head;

        // 快慢指针同步前进，相交点就是环起点
        while (slow != fast) {
            fast = fast->next;
            slow = slow->next;
        }
        return slow;
    }
};
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

[外链图片转存中…(img-1Kmjiqce-1696404256362)]

454. 四数相加II

使用hashtable保存sum和sum的出现次数，将时间复杂度降低到O(n2)

class Solution {
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
        int count = 0;
        unordered_map<int, int> tb;//key是和，value是出现次数
        for(int num1 : nums1){
            for(int num2 : nums2){
                tb[num1 + num2]++;
            }
        }
        for(int num3 : nums3){
            for(int num4 : nums4){
                auto iter = tb.find(0 - (num3 + num4));
                if(iter != tb.end()){
                    count += iter->second;
                }
            }
        }
        return count;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

383. 赎金信

也是一个数组做hashtable加加减减的事，直接过