目录经典例题复现1移动零算法思路快慢指针算法流程解题代码时间复杂度分析2复写零算法思路反向回填同向双指针算法流程解题代码时间复杂度分析3盛水最多的容器算法思路对撞指针算法流程解题代码算法总结快慢指针反向回填同向双指针对撞指针经典例题复现1移动零题目链接283. 移动零 - 力扣LeetCode理解题意在原数组的基础上操作将给定数组中的所有零元素移到末尾。双指针算法被常用作数组分块操作序列中的元素等题目本题很明显是数组分块可利用快慢指针将数组分成两部分——非零元素和零元素。算法思路快慢指针定义两个指针分别是cur和destcur指针用来扫描数组中的元素dest指针用来记录最后一个非零元素的位置。根据在cur扫描数组的过程中遇到的不同情况采取不同的措施实现数组划分。cur扫描完毕之后数组将被划分成两个区域[ 0,dest ] 区间的非零元素[ dest1,cur-1 ]区间的零元素。算法流程初始值cur 0 ,dest -1;dest始终指向最后一个非零元素所以还未开始扫描时指向空。cur 开始扫描数组。当 cur 位置上是 0 直接 cur 以保证 [ dest1,cur-1 ]区间是零元素当 cur 位置上是非零元素 dest因为dest始终指向最后一个非零元素将dest位置上的元素和cur位置数的元素交换。完事之后cur以例题1为例如图解题代码Java版本代码如下:class Solution { public void moveZeroes(int[] nums) { //1.定义指针 int cur0; int dest-1; //2.遍历数组元素 while(curnums.length){ //3.分类处理 if(nums[cur]0){ cur; }else{ dest; swap(dest,cur,nums); cur; } } } //交换数组元素位置方法 public void swap(int a,int b,int[] nums){ int temp nums[a]; nums[a] nums[b]; nums[b] temp; } }C版本代码如下:class Solution { public: void moveZeroes(vectorint nums) { for(int cur 0, dest -1; cur nums.size(); cur) { if(nums[cur]) // 处理非零元素 { swap(nums[dest], nums[cur]); } } } };时间复杂度分析整个移动过程只需要 cur 遍历完一遍数组元素即可完成数组划分则时间复杂度为O(n)n为数组的元素个数。2复写零题目链接1089. 复写零 - 力扣LeetCode理解题意在原来的数组上操作将数组中的每个0元素都再写一遍放到数组中其他元素向右平移数组长度不能改变。由于要复写元素那么就需要一个人来记住要被复写的元素另一个人复写这就涉及到读操作和写操作的概念了试想一下如果从左向右复写写操作的前提是要读但写的速度大于读的速度那么势必就会产生错误因为此时读的数据就是已经被写过的数据。本题可采用反向回填同向双指针解决。算法思路反向回填同向双指针从左向右不行那就从右向左复写元素。定义两个指针cur 初始值0和dest初始值-1。首先就需要找到最后一个被复写的元素cur从左向右扫描元素dest 根据cur所在位置上的元素状态0 / 非0决定走几下当dest走到数组末端或越界cur的位置就是最后一个被复写的元素。先判断dest是否越界若越界则进行处理处理后则开始复写cur位置的元素到dest位置的元素。这时候有人就会比较疑问为什么要先找到最后一个被复写的元素为什么dest初始值是-1答①由于要再复写以便数组中的0元素那么在数组中有0元素的情况下势必会导致元素个数超过数组长度那么末尾的元素就会被丢掉那你从最后一个元素开始复写不就会把数组最前面的元素给丢掉了嘛那结果就一定会是错的啊。所以需要找到最后一个被复写的元素才能开始复写。②我们要根据cur位置上的值去决定dest一次走几步复写几遍去找最后一个被复写的元素如果一开始dest就在0位置上实际上就走了一步了dest始终会多走一步就会导致元素找错。算法流程1.初始值 cur 0dest -1先找到最后一个被复写的元素1.1 先判断cur位置数的元素▸cur位置上的值为非0dest;▸ cur位置上的值为0dest21.3 最后cur;2.预备开始复写2.1 先判断dest是否越界destlen (数组长度)▸dest越界数组最后一个元素直接改成0dest2;▸dest没越界开始复写。2.2 开始复写▸若cur位置为非0arr[dest] arr[cur]▸若粗人位置上为0arr[dest] 0; arr[dest] 0; cur;重复2.2步骤知道数组遍历完复写也就完毕了。以例题1为例如图解题代码Java版本代码如下:class Solution { public void duplicateZeros(int[] arr) { int cur0; int dest-1; int narr.length; //1.找到最后一个被复写的元素位置 while(curn){ if(arr[cur]0) dest2; else dest; if(destn-1) break; cur; } //2.处理边界情况 if(destn){ arr[n-1]0; dest-2; cur--; } //3.开始复写 while(cur0){ if(arr[cur]0){ arr[dest--]0; arr[dest--]0; cur--; }else{ arr[dest--]arr[cur--]; } } } }C版本代码如下:class Solution { public: void duplicateZeros(vectorint arr) { // 1. 先找到最后一个数 int cur 0, dest -1, n arr.size(); while(cur n) { if(arr[cur]) dest; else dest 2; if(dest n - 1) break; cur; } // 2. 处理一下边界情况 if(dest n) { arr[n - 1] 0; cur--; dest - 2; } // 3. 从后向前完成复写操作 while(cur 0) { if(arr[cur]) { arr[dest--] arr[cur--]; } else { arr[dest--] 0; arr[dest--] 0; cur--; } } } };时间复杂度分析寻找最后一个被复写的元素从前向后遍历—O(n)从后向前复写数组元素—O(n) O(n) O(n) O(n)。3盛水最多的容器题目链接11. 盛最多水的容器 - 力扣LeetCode理解题意本题就是要找到两个元素的值与下标之差x轴所围成面积的最大值。本题可采用暴力解题思路枚举任意两个元素计算面积最后找到最大值。但这样做势必会导致超时所以不建议使用暴力解法。由于要找到两边的元素作为 “桶边” 所以不妨采用对撞指针解决该问题。算法思路对撞指针首先定义左右指针——leftfight分别位于数组的左右两侧两个指针相当于 “桶边” 如图就拿这个数组 [ 1,8,6,2,5,4,8,3,7 ] 例最开始left在0下标位置fight在数组末尾此时left位置上的值明显小于right位置上的数值根据木桶效应可知若left不动无论right怎么移动此时围成的面积值只会变小所以只能移动left值。后续持续这样的操作通过每次只移动一个边界就可以免去很多不必要的枚举从而达到提高效率的目的。当left与right相遇时这期间产生的所有容量值中的最大值就是我们要找的值。算法流程1. 对撞指针初始值left 0right len-1数组长度-12. 先计算“容量”v ( right - left ) * min(height [ left ]height [ right ])。与上一次计算的v值作比较保留较大者。3.比较left位置与right位置上的值▸若height [ left ] height [ right ]left▸若height [ left ] height [ right ]right--4.循环步骤3直到 leftright此时的v值就是最大容量解题代码Java版本代码如下:class Solution { public int maxArea(int[] height) { //1.定义对撞指针 int left0; int rightheight.length-1; int maxV0; //2.循环比较 while(left!right){ int curV (right-left)*Math.min(height[left],height[right]); maxV Math.max(maxV,curV); if(height[left]height[right]) left; else right--; } return maxV; } }C版本代码如下:#include vector #include algorithm using namespace std; class Solution { public: int maxArea(vectorint height) { int left 0, right height.size() - 1, ret 0; while(left right) { int v min(height[left], height[right]) * (right - left); ret max(ret, v); if(height[left] height[right]) left; else right--; } return ret; } };时间复杂度分析对撞指针的效率一般是双指针算法中最高的从两头开始遍历时间复杂度O(n/2)—O(n)。相较于暴力解法O(n²),效率高太多了。算法总结双指针算法一般分为两类同向双指针和反向双指针对撞指针。同向双指针又分为快慢指针和反向回填同向双指针但面对不同的应用场景我们要学会选择合适的算法快慢指针特征 快慢指针一般适用于同起点、同一个方向但是步长不同快指针跑的更快慢指针跑的更慢。但绝大多是单链表使用的较多数组用的相对较少。使用场景判断链表中是否有环、环入口找链表中的点删除链表中倒数第k个节点模板特征以Java为例ListNode slow head; ListNode fast head; while (fast ! null fast.next ! null) { slow slow.next; fast fast.next.next; }推荐例题快去练练叭~142. 环形链表 II - 力扣LeetCode234. 回文链表 - 力扣LeetCode反向回填同向双指针特征同向都从左往右走读指针 i 不断向前走写指针在后面只有满足一定条件才写入写完 j使用场景原地修改数组、除去不需要的元素保留有效元素在某位置。模板特征以Java为例// j写指针i读指针都从左往右 int j 0; for (int i 0; i nums.length; i) { if (满足保留条件) { nums[j] nums[i]; j; } } // j 就是有效元素长度 return j;推荐例题快去练练叭~27. 移除元素 - 力扣LeetCode80. 删除有序数组中的重复项 II - 力扣LeetCode对撞指针特征left再开头right在结尾相向而行一般不修改原数组用来查找和计算。使用场景有序数组两数之和、三数之和判断回文、反转数组。模板特征以Java为例int left 0, right n - 1; while(left right) { // 判断 if(xxx) left; else right--; }推荐例题快去练练叭~125. 验证回文串 - 力扣LeetCode15. 三数之和 - 力扣LeetCode好啦关于优选算法中的双指针算法的相关总结就给大家分享到这儿啦后续我还会持续分享其他算法的相关总结都在我的《算法》专栏中哦感兴趣的小伙伴们不妨关注博主下期见~~