复习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;}
};

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;}
};

[外链图片转存中…(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;}
};