Home
Problem
Status
Contest
Workbook
User
Group
Forum
Register
Login
{"workbook":{"problemsBrief":"{\"洛谷-P1102\":[\"A-B 数对\",91446,null],\"洛谷-P2642\":[\"双子序列最大和\",3723,null],\"洛谷-P8889\":[\"狠狠地切割 (Hard Version)\",750,\"入门赛 #7\"],\"洛谷-B3737\":[\"双十一\",1487,\"信息与未来 2018\"],\"洛谷-P7714\":[\"排列排序\",2775,\"EZEC-10\"],\"洛谷-P8160\":[\"星际蛋糕 (Intercastellar)\",1309,\"JOI 2022 Final\"],\"洛谷-P9914\":[\"匀速相遇\",960,\"RiOI-03\"],\"洛谷-P1638\":[\"逛画展\",23184,null],\"洛谷-P1096\":[\"Hanoi 双塔问题\",22926,\"NOIP2007 普及组\"],\"洛谷-P9950\":[\"Mad Scientist B\",598,\"USACO20FEB\"]}","joined":false,"groups":{}},"managingGroups":{},"author":"Exile_code","updateTime":1706767348000,"title":"基础算法入门(双指针)","dislikeCnt":0,"content":"# 基础算法入门(双指针)\n\n## 双指针算法思想\n\n双指针算法是一种常用于数组和链表等数据结构的算法,其核心思想是使用两个指针在数组或链表中进行遍历,常见的类型有快慢指针、左右指针、同向双指针和反向双指针。\n\n## 快慢指针\n\n快慢指针主要用于解决链表中的问题。通过设定两个指针,一个移动速度较快,一个移动速度较慢,来遍历链表。这种方法常用于检测链表中是否存在环,或者寻找链表的中间节点。\n\n```cpp\n// 快慢指针 - 检测链表中是否存在环\nbool hasCycle(ListNode* head) \n{\n ListNode* slow \u003d head;\n ListNode* fast \u003d head;\n\n while (fast !\u003d nullptr \u0026\u0026 fast-\u003enext !\u003d nullptr) \n {\n slow \u003d slow-\u003enext; // 慢指针每次移动一步\n fast \u003d fast-\u003enext-\u003enext; // 快指针每次移动两步\n\n if (slow \u003d\u003d fast)\n return true; // 链表中存在环\n }\n\n return false; // 链表中不存在环\n}\n```\n\n## 左右指针\n\n左右指针主要用于解决数组或字符串中的问题。通过设定两个指针,一个从数组的左侧开始移动,一个从右侧开始移动,来遍历数组。这种方法常用于在数组中寻找一对满足某种条件的元素,或者进行数组的夹逼操作。\n\n```cpp\n// 左右指针 - 在有序数组中寻找一对元素的和等于目标值\nvector\u003cint\u003e twoSum(vector\u003cint\u003e\u0026 numbers, int target) \n{\n int left \u003d 0;\n int right \u003d numbers.size() - 1;\n\n while (left \u003c right)\n {\n int sum \u003d numbers[left] + numbers[right];\n\n if (sum \u003d\u003d target) \n return {left + 1, right + 1}; // 找到满足条件的一对元素\n else if (sum \u003c target)\n left++; // 调整左指针\n else\n right--; // 调整右指针\n }\n return {}; // 未找到满足条件的元素对\n}\n```\n\n## 同向双指针(滑动窗口)\n\n同向双指针,也称为滑动窗口,主要用于解决数组或字符串中的子数组或子字符串问题。通过维护一个窗口,通常是两个指针之间的区域,在数组上滑动,来寻找满足条件的子数组或子字符串。\n\n```cpp\n// 同向双指针 (滑动窗口) - 寻找最小子数组长度,使得和大于等于目标值\nint minSubArrayLen(int target, vector\u003cint\u003e\u0026 nums) \n{\n int left \u003d 0;\n int sum \u003d 0;\n int minLength \u003d INT_MAX;\n\n for (int right \u003d 0; right \u003c nums.size(); ++right) \n {\n sum +\u003d nums[right];\n\n while (sum \u003e\u003d target) \n {\n minLength \u003d min(minLength, right - left + 1);\n sum -\u003d nums[left];\n left++;\n }\n }\n\n return minLength \u003d\u003d INT_MAX ? 0 : minLength;\n}\n\n```\n\n## 反向双指针\n\n反向双指针常用于数组或字符串中的问题,与左右指针类似,但是移动方向相反。常用于对数组进行翻转或寻找一对满足某种条件的元素。\n\n```cpp\n// 反向双指针 - 反转字符串\nvoid reverseString(vector\u003cchar\u003e\u0026 s)\n{\n int left \u003d 0;\n int right \u003d s.size() - 1;\n\n while (left \u003c right) \n {\n swap(s[left], s[right]);\n left++;\n right--;\n }\n}\n\n```\n\n## 适用场景\n\n- **快慢指针**:适用于链表中的环检测、链表的中间节点查找等问题。\n- **左右指针**:适用于数组或字符串中的夹逼问题,如在有序数组中寻找一对元素的和等于目标值。\n- **同向双指针**:适用于数组或字符串中的子数组或子字符串问题,如最小子数组长度等。\n- **反向双指针**:适用于数组或字符串中的元素翻转或寻找一对满足条件的元素。\n\n## 注意事项\n\n1. **初始化指针位置**:在使用双指针算法时,需要注意初始化指针的位置,确保能够涵盖整个搜索范围。\n2. **指针移动条件**:在移动指针时,需要根据具体问题设定移动的条件,防止死循环或越界。\n3. **适用性**:双指针算法通常适用于数组或链表中具有特定结构的问题,需要灵活运用。\n\n## 学习链接\n\n[【双指针超清晰动画演示】从一个简单模型到双指针三大经典应用: 三数之和 归并排序 快速排序(上集)_哔哩哔哩_bilibili](https://www.bilibili.com/video/BV1kC4y1A75i/?vd_source\u003d204bd6a950e12dc2a5fd501f88a334d9)\n\n[一个视频带你彻底搞懂双指针算法——链表4:力扣2130.链表最大孪生和(中等题)_哔哩哔哩_bilibili](https://www.bilibili.com/video/BV1Gt4y1A7Ei/?vd_source\u003d204bd6a950e12dc2a5fd501f88a334d9)\n\n## 练习题目\n\n[problem:洛谷-CF1793C],[problem:洛谷-P9950],[problem:洛谷-P7714],[problem:洛谷-P8160],[problem:洛谷-P1102],[problem:洛谷-P8889],[problem:洛谷-B3737],[problem:洛谷-P9914],[problem:洛谷-P2642],[problem:洛谷-P1096],[problem:洛谷-P1638]","threadId":181200,"likeCnt":0,"createTime":1706767348000,"isWorkbook":true,"viewCnt":181,"openness":2,"fav":false,"id":4542,"trustable":false}