💖 ❄️我们的算法之路❄️💖
众所周知，作为一名合格的程序员，算法 能力 是不可获缺的，并且在算法学习的过程中我们总是能感受到算法的✨魅力✨。
☀️🌟短短几行代码，凝聚无数前人智慧；一个普通循环，即是解题之眼🌟☀️
💝二分，💝贪心，💝并查集，💝二叉树，💝图论，💝深度优先搜索(dfs) ，💝宽度优先搜索（bfs） ，💝数论，💝动态规划等等， 路漫漫其修远兮，吾将上下而求索！ 希望在此集训中与大家共同进步，有所收获！！！🎉🎉🎉
今日主题：双指针
👉⭐️第一题💎
✨题目
✨思路：
双指针解法，对于有序数组,不需要回溯,对每条边比较两边大小，取较小的数放到nums1中（这里直接暴力排序做的）,然后另一个指针不动,这个指针继续往下走,两边继续比较,直到有一方指针造成数组越界,然后将剩余数加到排序数组里
✨代码：
class Solution { public: void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) { vector<int>temp(m+n); int j=0; for(int i=0;i<m;i++){ temp[j++]=nums1[i]; } for(int i=0;i<n;i++){ temp[j++]=nums2[i]; } sort(temp.begin(),temp.end()); nums1=temp; } };
👉⭐️第二题💎
✨题目
快慢指针法，假设慢指针每次只移动一步，而快指针每次移动两步。如果在移动的过程中，快指针反过来追上慢指针，就说明该链表为环形链表。否则快指针将到达链表尾部，该链表不为环形链表。
✨代码：
class Solution { public: bool hasCycle(ListNode* head) { if (head == nullptr || head->next == nullptr) { return false; } ListNode* slow = head; ListNode* fast = head->next; while (slow != fast) { if (fast == nullptr || fast->next == nullptr) { return false; } slow = slow->next; fast = fast->next->next; } return true; } };
👉⭐️第三题💎
✨题目
✨思路：
首先不考虑暴力枚举，因为题目中要求找到所有不重复的三元组，暴力的话时间复杂度就太高了，所以这里选择 双指针与排序解法
✨代码：
class Solution { public: vector<vector<int>> threeSum(vector<int>& nums) { int n = nums.size(); sort(nums.begin(), nums.end()); vector<vector<int>> ans; for (int first = 0; first < n; ++first) { if (first > 0 && nums[first] == nums[first - 1]) { continue; } int third = n - 1; int target = -nums[first]; for (int second = first + 1; second < n; ++second) { if (second > first + 1 && nums[second] == nums[second - 1]) { continue; } while (second < third && nums[second] + nums[third] > target) { --third; } if (second == third) { break; } if (nums[second] + nums[third] == target) { ans.push_back({nums[first], nums[second], nums[third]}); } } } return ans; } };
写在最后：
相信大家对今天的集训内容的理解与以往已经有很大不同了吧，或许也感受到了算法的魅力,当然这是一定的，路漫漫其修远兮，吾将上下而求索！伙伴们，明天见！
