欢迎来到 s a y − f a l l 的文章 欢迎来到say-fall的文章欢迎来到say−fall的文章say-fall个人主页专栏《手把手教你学会C》 | 《C语言从零开始到精通》 | 《数据结构与算法》 | 《小游戏与项目》格言做好你自己才能吸引更多人与他们共赢这才是最好的成长方式。前言基于数据结构的扎实基础算法思想能够有效提升问题解决的效率。为此我们开设一个专门的算法专栏用来探讨各类算法题目的解决方案。在算法学习的道路上双指针是一种简洁、高效且应用广泛的解题思想它并非局限于某一种特定的数据结构而是一种通过设置两个“标记点”指针协同遍历、筛选或修改数据从而简化问题复杂度的核心思路。无论是数组、链表的遍历处理还是数值组合、环形问题的求解双指针都能发挥其独特优势——相较于暴力枚举的多层循环它往往能将时间复杂度从O(n²)优化至O(n)大幅提升代码运行效率同时让解题逻辑更清晰、代码更简洁易懂。本文将系统拆解双指针算法的核心逻辑按“快慢双指针”“首尾双指针”“快慢双指针解决环形问题”三大类别结合LeetCode经典例题如移动零、盛水最多的容器、三数之和、环形链表等从算法思想、解题步骤、代码实现三个维度手把手带你掌握双指针的用法。每道例题均搭配详细解析和优化思路兼顾基础入门与进阶提升帮助你真正理解双指针的核心逻辑。文章目录前言正文零、什么是双指针一、快慢双指针0. 算法思想1. 双指针快排思想2. 双指针移动零3. 复写零三、首尾双指针0. 算法思想:1. 双指针移动零2. 盛水最多的容器3. 两数之和4. 三数之和5. 有效三角形的个数6. 四数之和三、快慢双指针解决环形问题0. 算法思想1. 环形链表2. 快乐数正文零、什么是双指针需要说明的是双指针并不局限于字面意义上的两个指针而是通过标记两个目标点来简化问题的解决思路。接下来我们通过具体实例深入解析这一算法。一、快慢双指针0. 算法思想前后快慢指针以慢指针为基准划分界限慢指针左侧包括其指向的元素均小于等于基准值右侧均大于基准值或者是慢指针左或者右为同一元素。1. 双指针快排思想快速排序最初由霍尔Hoare提出其算法逻辑相对复杂。为便于理解后来发展出了前后指针法实现快排。以下是详细说明注本文提到的指针并非真正意义上的指针而是数组的索引下标关键概念说明key [基准值]prev [慢指针]cur [快指针]首先选择最左侧元素作为基准值key初始化prev指针与key同位置cur指针指向下一个位置当cur指向的元素小于key时移动prev指针并与cur进行元素交换可以避免原地互换cur指针持续移动遇到比基准值小的元素时暂停此时移动prev指针并进行交换非原地交换会将较小元素移至prev位置重复上述过程直到cur指针越界最后交换key与prev指向的元素确保基准值左侧元素均小于它右侧元素均大于它//双指针法快排intptrSort(int*a,intleft,intright){intkeyileft;intprevleft,curleft1;while(curright){if(a[cur]a[keyi]){prev;if(a[cur]!a[prev]){Swap(a[cur],a[prev]);}}cur;}Swap(a[keyi],a[prev]);returnprev;}至此完成对基准值的排序之后只需递归地对左右两个子区间执行相同操作一般使用递归即可完成整个数组的排序。2. 双指针移动零题目leetcode:移动零移动零问题可以类比为以零为基准的单次快速排序初始化两个指针cur指向数组首元素prev初始化为-1遍历过程中当cur遇到非零元素时prev右移一位并与cur交换元素否则cur继续右移重复上述过程直至cur到达数组末尾classSolution{public:voidmoveZeroes(vectorintnums){for(intcur0,dest-1;curnums.size();cur)if(nums[cur])swap(nums[dest],nums[cur]);}};3. 复写零题目leetcode:复写零处理复写零问题的关键在于确定结束位置。以下是优化后的双指针解决方案初始化指针将cur和dest都指向数组首元素然后cur开始移动遍历规则当cur指向0时dest移动两步当cur指向非零元素时dest移动一步终止条件当dest到达数组末尾时停止边界处理若cur指向最后一个元素为0时dest可能越界此时需要将dest回退两位并将末尾元素置零同时cur回退一位逆向复写由于已精确计算复写元素数量无需担心原地复写导致的覆盖问题classSolution{public:voidduplicateZeros(vectorintarr){//双指针找最后一个复写的数intcur0,dest-1,narr.size();while(1){if(arr[cur]0)dest;dest;if(destn-1)break;//找到退出cur;}//处理特殊情况if(destarr.size()){cur--;dest-2;arr[arr.size()-1]0;}//从后向前复写while(cur0){if(arr[cur]0)arr[dest--]arr[cur];arr[dest--]arr[cur];cur--;}}};三、首尾双指针0. 算法思想:首尾分别设定指针可以交换元素解决移动零类似问题也可以利用单调性解决其他问题1. 双指针移动零题目leetcode:移动零如果不需要保持元素的先后顺序的话也可以使用首尾双指针法设置左右指针left和rightleft找0right找非零元素交换直到左右指针相遇classSolution{public:voidmoveZeroes(vectorintnums){intleft0,rightnums.size()-1;while(leftright){if(nums[left])left;if(nums[right]0)right--;if(leftrightnums[left]0nums[right]!0)swap(nums[left],nums[right]);}}};2. 盛水最多的容器题目leetcode盛水最多的容器解法一本题可以使用暴力解法来计算即两层循环计算出 “体积” 取其最大值。解法二根据体积的计算公式 v w * h 先排序得到一个有顺序的数组首尾设定指针向内移动宽度w必定减小高度由于取最小值会降低或者不变则说明计算出体积v以后将二者高度较小的一方排除向内移动即可减少遍历次数classSolution{public:intgetv(vectorintheight,intleft,intright){intwidthright-left;inthighheight[right];//假设法if(height[left]height[right]){highheight[left];}returnwidth*high;}intmaxArea(vectorintheight){intleft0;intrightheight.size()-1;intv0;while(leftright){intvvgetv(height,left,right);if(height[left]height[right])left;elseright--;if(vvv)vvv;}returnv;}};3. 两数之和题目两数之和解法一双层循环暴力枚举出所有可能值找到两数之和为目标的两个数。解法二先排序依旧设定首尾指针于是存在如果两指针所指元素之和小于目标值:变小一定得不到目标值所以右指针不能左移左指针右移如果两指针所指元素之和大于目标值:变大一定得不到目标值所以左指针不能右移右指针左移遍历直到找到和为目标值的两个数classSolution{public:vectorinttwoSum(vectorintprice,inttarget){intleft0,rightprice.size()-1;while(leftright){if(price[left]price[right]target)right--;elseif(price[left]price[right]target)left;elsereturnvectorint({price[left],price[right]});}returnvectorint();}};4. 三数之和题目三数之和三数之和实际上是两数之和的变式解法一与两数之和相同三层循环可以枚举出想要结果找到以后加入数组即可解法二依旧可以先排序然后固定首尾其中一个数字依次顺序固定重复元素跳过用两数之和类似双指针法计算出三数之和为结果的数字需要注意的是重复元素跳过最后遍历完成结果加入二维数组classSolution{public:vectorvectorintthreeSum(vectorintnums){//优化sort(nums.begin(),nums.end());intnnums.size();//利用单调性定尾部前面走双指针vectorvectorintvv;for(intin-1;i2;i--){if(in-1nums[i]nums[i1]){continue;}intleft0,righti-1;while(leftright){if(nums[left]nums[right]nums[i]0)right--;elseif(nums[left]nums[right]nums[i]0)left;else{// 找到符合条件的三元组加入结果vv.push_back({nums[left],nums[right],nums[i]});// 跳过左指针重复值while(leftrightnums[left]nums[left1])left;// 跳过右指针重复值while(leftrightnums[right]nums[right-1])--right;// 双指针收缩继续找下一组left;--right;}}}returnvv;}};5. 有效三角形的个数题目有效三角形的个数实际上本题也算是三数之和的变式只不过本体要求三数组成三角形而不是和为零解法一三层循环遍历枚举解法二先排序依旧固定一边利用三角形两小边之和大于第三边性质寻找三个符合要求的边符合要求则计入次数classSolution{public:inttriangleNumber(vectorintnums){intnnums.size()-1;sort(nums.begin(),nums.end());intsum0;for(intin;i0;i--){intleft0,righti-1;while(leftright){if(nums[left]nums[right]nums[i]){sumright-left;right--;}elseleft;}}returnsum;}};6. 四数之和题目四数之和这里不再讲解原理原理与三数之和类似直接看代码提一点本题需要注意的是样例里面存在超大数所以需要注意 int 无法承载的问题classSolution{public:vectorvectorintfourSum(vectorintnums,inttarget){intnnums.size();sort(nums.begin(),nums.end());vectorvectorintvv;for(intjn-1;j3;j--){if(jn-1nums[j]nums[j1])continue;intttarget-nums[j];for(intij-1;i2;i--){if(ij-1nums[i]nums[i1])continue;intleft0,righti-1;while(leftright){if((longlong)nums[left]nums[right]nums[i](longlong)t)left;elseif((longlong)nums[left]nums[right]nums[i](longlong)t)right--;else{vv.push_back({nums[left],nums[right],nums[i],nums[j]});while(leftrightnums[left]nums[left1])left;while(leftrightnums[right]nums[right-1])right--;left,right--;}}}}returnvv;}};三、快慢双指针解决环形问题0. 算法思想用跑圈的问题来类比如果一个快的人和慢的人在环形跑道跑步如果他们一直是恒速前进那么必定相遇快慢双指针也类似这个问题1. 环形链表程序员遇到的经典环形问题是leetcode环形链表问题采用快慢指针的思想如果有环就必定能相遇而如果没环必定能越界/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */classSolution{public:boolhasCycle(ListNode*head){typedefstructListNodeListNode;ListNode*fasthead;ListNode*slowhead;while(fast!NULLfast-next!NULL){fastfast-next-next;slowslow-next;if(slowfast){returntrue;}}returnfalse;}};2. 快乐数题目leetcode快乐数本题的两种情况其实可以看作是一种情况有环环内无1成一个大环有环环内只有1可看作一循环即为快乐数所以只需要判断快慢指针相遇的时候他们所指元素的值是不是1即可判断是否是快乐数classSolution{public:intget_sosq(intn)//获取平方和{intsum0;while(n){sumpow((n%10),2);n/10;}returnsum;}boolisHappy(intn){intshown,fastn;showget_sosq(show);fastget_sosq(fast);fastget_sosq(fast);while(show!fast){showget_sosq(show);fastget_sosq(fast);fastget_sosq(fast);}if(fast1)returntrue;returnfalse;}};本节完…