优选算法——双指针算法原理力扣题文章摘要本文深入解析双指针算法的核心思想与实战应用涵盖同向、相向、快慢指针三大经典场景。通过移动零、复写零、快乐数、盛最多水的容器、有效三角形的个数、和为s的两个数、三数之和等七道力扣高频题目系统讲解算法原理、解题思路与代码实现助你快速掌握双指针技巧提升算法解题效率。目录1.移动零2.复写零3.快乐数4.盛最多水的容器5.有效三角形的个数6.和为s的两个数7.三数之和双指针简介常⻅的双指针有两种形式⼀种是对撞指针⼀种是快慢指针。对撞指针⼀般⽤于顺序结构中也称左右指针。对撞指针从两端向中间移动。⼀个指针从最左端开始另⼀个从最右端开始然后逐渐往中间逼近。对撞指针的终⽌条件⼀般是两个指针相遇或者错开也可能在循环内部找到结果直接跳出循环也就是left right 两个指针指向同⼀个位置left right 两个指针错开快慢指针⼜称为⻳兔赛跑算法其基本思想就是使⽤两个移动速度不同的指针在数组或链表等序列结构上移动。这种⽅法对于处理环形链表或数组⾮常有⽤。其实不单单是环形链表或者是数组如果我们要研究的问题出现循环往复的情况时均可考虑使⽤快慢指针的思想。快慢指针的实现⽅式有很多种最常⽤的⼀种就是在⼀次循环中每次让慢的指针向后移动⼀位⽽快的指针往后移动两位实现⼀快⼀慢。正文1.移动零题目链接移动零题目描述算法原理双指针定义数组下标模拟指针cur:用来遍历数组dest:指向已经处理过的区间内非零元素的最后一个元素大概思路先定义两个指针cur用来遍历数组从第一个元素开始遍历所以cur0dest用来指向处理过的数组中最后一个非零元素cur等于0还没有进行处理所以dest-1;当nums[cur]!0,交换nums[cur],num[dest];直到遍历整个数组代码:2.复写零题目链接复写零题目描述算法原理双指针定义数组下标模拟指针cur:遍历需要复写的部分数组dest:指向已经复写的最后一个元素大概思路由于从前往后复写时就地解决遇到零时要复写两次会导致后面没有被cur遍历的元素被覆盖。因此我们考虑从后往前复写。从后往前复写1.cur找到最后一个要复写的数1.1判断cur的值1.2.决定dest走一步还是两步1.3.判断dest是否越界1.4.cur2.考虑特殊情况当最后一个复写数是0复写两次但是在复写之前dest已经到达了arr.length-2,复写两次会导致destarr.lenth导致数组越界。这个时候就要我们手动处理最后一个要复写的数即0只需要复写一遍。给出一组特殊情况的数组可自己模拟[1,0,2,3,0,4]3.从后往前复写0复写一边0复写两边代码3.快乐数题目链接快乐数题目描述算法原理快慢双指针定义数组下标模拟指针slow每次走一步fast:每次走两步大概思路问题转化将数字按“快乐数”规则每位平方和不断迭代看作一个隐式的链表。每个数字是链表的一个节点其下一个节点是它各位平方和得到的数字。判断循环如果迭代过程中出现1则链表到达“终点”该数是快乐数。如果进入循环即出现之前出现过的数字则该数不是快乐数。快慢指针法定义两个“指针”slow和fast初始都等于原始数字n。slow每次计算一次各位平方和走一步fast每次计算两次各位平方和走两步。如果fast最终等于1说明是快乐数。如果fast和slow相遇值相等且不等于1说明进入了循环不是快乐数。代码4.盛最多水的容器题目盛最多水的容器题目描述算法原理相撞双指针定义数组下标模拟指针left:水柱左侧right:水柱右侧大概思路代码5.有效三角形的个数题目链接有效三角形的个数题目描述算法原理双指针left:指向aright:指向b法一暴力枚举但是会超时法二利用单调性使用双指针大概思路固定最大数c在最大数的左区间使用双指针算法根据最小的两边之和大于第三边即abc快速统计出符合要求的三元组的个数代码6.和为s的两个数题目链接和为s的两个数题目描述大概思路问题转化在递增排序的数组中寻找两个数使它们的和等于目标值target。双指针法初始化两个指针left指向数组起始位置最小元素right指向数组末尾最大元素。计算当前和sum nums[left] nums[right]。如果sum target找到答案返回这两个数。如果sum target说明当前和太小需要增大因此left右移选择更大的数。如果sum target说明当前和太大需要减小因此right左移选择更小的数。代码7.三数之和题目链接三数之和题目描述大概思路1.排序2.固定一个数nums[i];3.在该数的后面区间利用“双指针算法”快速找到两个数为-nums[i](此步原理同求两数之和的算法原理细节问题1.去重找到一种结果之后 left和right要跳过重复的元素使用完一次双指针之后i也要跳过重复的元素。2.不漏找到一种结果之后缩小区间继续找。代码练习四数之和提示排序固定一个数三数之和算法原理同样注意去重