在前言中，我刚刚完成了上一部分的分叉和滑动窗口。它们都属于特殊的双指针写法，所以这部分直接总结除特殊分叉和滑动窗口之外的其他双指针写法。这里主要是速度指针和终点指针。一些遍历一次做不完的题，多点指点也不累，感觉基本属于一种解题思路。如果它一次不起作用，我会看起来像它两次；所以我就完成了基本的双指针，然后滑动窗口两个点之后，这种思路在以后的解题中应该时不时的冒出来；所以下一期学习另一种解决问题的方法，我们回去吧；文字双指针已经被用在许多常用的数据结构和算法中。使用，比如在遍历链表的过程中，可以使用双指针求中值，求环；在二分法中，还使用了双指针；滑动窗口，还有双滑动窗口等。所以双指针是解决问题的思路，当设置一个指针遍历不足以形成比较时，可以设置更多的引用指针为自己服务，但一般都是两个指针够了，所以这个方案叫做双指针快慢指针，比较常见的是双指针的形式，一般快指针走2步，慢指针走1步，达到对比效果；以链表的形式解决中位数的问题，链表有环；还有一个读写指针，也是一个指针读先走，触发一定条件后写再走，形成速度的效果；左右端点指针最常用的方法是二分法，即设置lr指针，然后靠近中间；所以所有二分法的使用也是双指针的使用。另一种是根据排序后最大值和最小值之间的运算来评价。这时需要端点指针查找重复值时，转成链表查找环。--快慢指针的变形做快慢指针题目的时候，乍一看题目跟快慢指针没什么关系，但一般都是迭代，或者重复取值等等。反正,有必要执行相同的操作。确定是否曾经出现过相同的值。这时候要么用hashMap缓存一波，要么用快慢指针把原题转换成类型链表的结构。next指针就是对应的迭代函数，然后问有没有Ring（202.快乐数），或者ring的入口位置（287.找重复数）当然上面是专题的特殊方法，比如287。找重复的数是因为这里的下标和value刚好不完全重合，存在重复。如果value也是来自[0,n-1]，那么就没办法用value作为下标了解决了相应的问题后，循环链表II就是针对这个问题做的，是针对pre-var的下一题的detectCycle=function(head){constemptyNode=newListNode()emptyNode.next=head;if(!head)returnnullletslow=fast=emptyNodewhile(fast&&fast.next){slow=slow.nextfast=fast.next.nextif(slow===fast){//相交，证明相交letnext=emptyNodewhile(next!==slow){next=next.nextslow=slow.next}//相交时，环入口是否returnslow}}returnnull}287.寻找重复数的分析——双指针法（快慢指针）考试：只有一个重复整数，这个重复整数出现的次数不确定。可以用map代替space排序后直接找时间也可以，但这不符合题意。之前在二分法选项卡里做过一次：287.找重复题可以用快指针和慢指针来做，就是把数组中的值当作指向数组下标的指针，然后将整个数组转换为链表；并将题目转化为循环链表（有重复值，即链表中有重复的指针），找到环的表项；参考find循环链表的入口——142.循环链表二的时间复杂度为O(N)varfindDuplicate=function(nums){letslow=fast=0//initialnodewhile(fast&&nums[fast]){slow=nums[slow]fast=nums[nums[fast]]if(slow===fast){让next=0while(next!==slow){slow=nums[slow]next=nums[next]}returnslow}}}分析给定长度n+1的nums，里面的值都是1-n，在这道题中只有一个值重复，找出这个值注意这里只说明只有一个重复的值，但是这个值重复了多少次并没有表示，所以我们不能用简单的异或二进制处理，但是我们可以选择mid值，然后判断小于等于mid值count，如果count超过mid，则证明[1,mid]中至少有一个值重复。这时候可以剪掉右边的部分。当左右相等时，找到唯一重复的值，因为此时左右两边的值不符合要求，这是唯一的时间复杂度O(nlohn)，空间复杂度1varfindDuplicate=function(nums){letleft=1,right=nums.length-1;//值为1-nwhile(left>1)+left;constcount=nums.reduce((prev,cur)=>(cur<=mid?prev+1:prev),0);//value小于等于countif(count>mid){//如果数组[1,mid]已满，只有mid的，现在如果count大于这个，证明这里是重复值右=中；}else{左=中+1;}}向左返回；};参考视频：传送门80.删除有序数组中的重复项二读写指针也分快慢指针一、读指针一般会先走，只有触发了某个条件后，才会移动写指针。有2次设置读写指针读写。在遍历的每一步中，读写指针都指向同一个值，但指向的下标可能不同。当同值超过2时，即[left,right]的长度超过2时，原地删除右指针指向的值时间复杂度O(n)varremoveDuplicates=function(nums){letwrite=read=0while(read2){nums.splice(read,1)//删除读指针的当前下标}else{read++}}//一轮同值完成，写指针和读指针指向同一个值write=read}};202.happynumbers分析这里盲猜是通过迭代写得到的，因为没有时间根据要求改造一个ret，如果不满足成功或者要求失败，就会继续迭代，因为它不断地按照小数位对平方进行求和，所以截止条件应该满足要求。如果得到的sum===1不满足条件，那一定是遇到了循环。这里我们使用set缓存了迭代过程中的所有ret，只有当set中的值在迭代过程中重新出现时，才会造成循环，直接返回false，得到时间复杂度。这不是很好，但它需要设置缓存数据varisHappy=function(n){constset=newSet()letresultconstdfs=n=>{letret=0;while(n){ret+=Math.pow(n%10,2);n=Math.floor(n/10);}如果（ret===1）{result=truereturn}if(set.has(ret)){result=falsereturn}set.add(ret)//迭代写法，如果return是递归写法dfs(ret);}dfs(n)returnresult};分析这是快慢指针的题目，所以其实可以通过快慢指针是否有环来处理，所以迭代过程和next的类似链表。如果出现环则返回false，如果出现值为1则返回true这样就不需要额外设置缓存值了varisHappy=function(n){functiongetNext(n){letret=0;while(n){ret+=Math.pow(n%10,2);n=Math.floor(n/10);}returnret}lets=f=n//初始化的值都是nwhile(f!==1&&getNext(f)!==1){s=getNext(s)f=getNext(getNext(f))if(s===f)returnfalse}returntrue}16.最接近的三数之和解析暴力解，直接固定左右节点i，j，然后设置第三个指针k遍历和在两个指针之间求和以找到最接近目标的值。i遍历一次nums，j和k加起来每隔固定时间遍历一次nums，所以时间复杂度为O(n2)varthreeSumClosest=function(nums,target){constlen=nums.lengthletret;lettemp=Infinity//sum和target之间的差异for(leti=0;i1;j--){for(letk=i+1;k=k&&l<=r){//超出kll=nums[l];产品=产品/ll;l++；}//此时[l,r]之间的值的乘积小于kret+=r-l+1;r++;返回ret；};977。有序数组的平方解析，分配了左右指针l，r，然后用一个额外的数组来存放平方数组。因为这是一个排序的递增序列，会有负数，但是正方形的最大值在数组的两边，所以每次比较两边的值，就可以得到对应的最大值，然后将其取消移位到数组中。时间复杂度O(n)，空间复杂度O(n)varsortedSquares=function(nums){letl=0,r=nums.length-1letret=[]while(l<=r){if(nums[r]>Math.abs(nums[l])){ret.unshift(Math.pow(nums[r],2))r--}else{ret.unshift(Math.pow(nums[l],2))l++}}返回ret};875。爱吃香蕉的珂珂解析--除以l=1,r=piles[max]，分别代表最大和最小速度；这样找出中间值，然后判断h小时内能不能吃到，能吃到就向左逼近，不能吃到后向右逼近，直到出现最小速度。每次取mid都要遍历piles一次，所以时间复杂度为nlognvarminEatingSpeed=function(piles,h){letl=1,r=piles.reduce((prev,cur)=>(prev>=cur?prev:cur),1);while(l<=r){constmid=((r-l)>>1)+l;如果（getHours（中）>h){//所需时间超过h，证明速度不够l=mid+1;}else{r=中-1;}}//当速度为v时，需要多长时间才能吃完functiongetHours(v){letret=0;for(leti=0;ia-b);让计数=0；//需要的船数while(l<=r){constsum=people[l]+people[r];if(sum>limit){r--;}否则{l++;r--;}计数++；}返回计数;};
