在前言中，我刚刚完成了上一部分的分叉和滑动窗口。它们都属于特殊的双指针写法，所以这部分直接总结除特殊分叉和滑动窗口之外的其他双指针写法。这里主要是速度指针和终点指针。一些遍历一次做不完的题，多点指点也不累，感觉基本属于一种解题思路。如果它一次不起作用，我会看起来像它两次；所以我就完成了基本的双指针，然后滑动窗口两个点之后，这种思路在以后的解题中应该时不时的冒出来；所以下一期学习另一种解决问题的方法，我们回去吧；文字双指针已经被用在许多常用的数据结构和算法中。使用，比如在遍历链表的过程中，可以使用双指针求中值，求环；在二分法中，还使用了双指针；滑动窗口，还有双滑动窗口等。所以双指针是解决问题的思路，当设置一个指针遍历不足以形成比较时，可以设置更多的引用指针为自己服务，但一般都是两个指针够了，所以这个方案叫做双指针快慢指针，比较常见的是双指针的形式，一般快指针走2步，慢指针走1步，达到对比效果；以链表的形式解决中位数的问题，链表有环；还有一个读写指针，也是一个指针读先走，触发一定条件后写再走，形成速度的效果；左右端点指针最常用的方法是二分法，即设置lr指针，然后靠近中间；所以所有二分法的使用也是双指针的使用。另一种是根据排序后最大值和最小值之间的运算来评价。这时需要端点指针查找重复值时，转成链表查找环。--快慢指针的变形做快慢指针题目的时候，乍一看题目跟快慢指针没什么关系，但一般都是迭代，或者重复取值等等。反正,有必要执行相同的操作。确定是否曾经出现过相同的值。这时候要么用hashMap缓存一波，要么用快慢指针把原题转换成类型链表的结构。next指针就是对应的迭代函数，然后问有没有Ring（202.快乐数），或者ring的入口位置（287.找重复数）当然上面是专题的特殊方法，比如287。找重复数是因为这里的下标和value刚好不完全重合，存在重复。如果value也是来自[0,n-1]，那么就没办法用value作为下标了。题目摘要速度指针环表二有序数组中查找重复项和删除重复项二离快乐数左右端点指针最近的三个数之和小于K.子有序数组的平方-大批（这里只有一个链接，具体可以去二分题看）模板1二分查找x的平方根猜数字的大小排列硬币搜索旋转排序数组模板2第一个错误版本找到peak查找旋转排序数组中的最小值查找旋转排序数组中的最小值II模板3查找排序数组中元素的第一个和最后一个位置找到K个最接近的元素ElsePow(x,n)有效完全平方求比目标字母大的最小字母二两个数组的交集两个数组的交集II两个数的和II-输入有序数组求重复次数4.求两个正序数组的中位数并相除数组的最大值滑动窗口（也属于双指针，感觉匹配快慢指针）找到字符串中所有字母变位词的最长子串，无重复字符最小子数组with最小覆盖子串长度904.水果篮与同二元子数组K个不同整数的最长子数组湍流子数组中连续1的最大个数III替换子串得到平衡串统计“美丽子-array》最小操作数个数使x减为0参考视频：传送门题目142.环形链表二典型快慢指针写法分析，我在链表题目中写了相应的题，解决了循环链表二。做下一道题的介词来做这道题吧。vardetectCycle=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用空间换时间，也可以排序后直接查找，但这不符合题意。我之前在二分法选项卡里做过一次：287.找重复数的题可以用快指针和慢指针来做，也就是把数组中的值看成是指向数组下标的指针，然后整个数组转换为链表；而题目变成了循环链表（有重复值，即链表中有重复的指针），找到环的入口；参考查找循环链表的入口——142。循环链表II的时间复杂度为O(N)varfindDuplicate=function(nums){letslow=fast=0//initialnodewhile(fast&&nums[fast]){slow=nums[slow]fast=nums[nums[fast]]if(slow===fast){letnext=0while(next!==slow){slow=nums[slow]next=nums[next]}returnslow}}}分析给定长度n+1的nums，里面的值是1-n。本题只重复了一个值。找出这个值。注意这里只有一个重复的值，但并不表示这个值重复了多少次，所以不能用简单的异或二进制处理，但是我们可以选择中间值，然后判断小于或等于中值计数。如果计数超过mid，则证明[1,mid]中至少有一个值重复。这时候可以在左右相等的情况下剪掉右边的部分。也就是找到唯一一个重复的值，因为此时左右两边的值都不符合要求，所以就只有这个了。时间复杂度O(nlohn)，空间复杂度1varfindDuplicate=function(nums){letleft=1,right=nums.length-1;//值为1-nwhile(left>1)+left;常量计数=nums。reduce((prev,cur)=>(cur<=mid?prev+1:prev),0);//小于或等于count的值if(count>mid){//如果数组[1,mid]已满，则只有中间的。现在如果count大于这个，就证明重复的值在这里Insideright=mid;}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.快乐数分析这里盲猜就是迭代这么写的，因为一个ret是永远不会按要求修改的。如果不满足成功或失败要求，就会继续迭代，因为它是不断的按照小数位对平方进行求和，所以截止条件应该满足要求，得到的sum===1如果条件不满足，必然循环。这里用set来缓存迭代过程中的所有ret。只有在迭代过程中集合中的值再次出现才会引起循环。直接返回false就可以得到时间复杂度，这个不太好，但是需要set来缓存数据varisHappy=function(n){constset=newSet()letresultconstdfs=n=>{letret=0;while(n){ret+=Math.pow(n%10,2);n=Math.floor(n/10);}if(ret===1){result=truereturn}if(set.has(ret)){result=falsereturn}set.add(ret)//迭代写法，如果用return就是递归写法dfs（退役）；}dfs(n)返回结果};分析是快慢指针的题目，所以其实可以用快慢指针是否有环来处理，所以迭代的过程类似于链表的next。如果出现环，则返回false，如果出现1的值，则返回true，所以不需要额外设置缓存值。varisHappy=function(n){functiongetNext(n){让ret=0;while(n){ret+=Math.pow(n%10,2);n=Math.floor(n/10);}返回ret}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在两个指针之间遍历Sum，找到最接近目标的值i遍历一次nums，j和k加起来每隔固定时间遍历一次nums，所以时间复杂度为O(n2)varthreeSumClosest=function(nums,target){constlen=nums.length让ret;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，然后使用一个额外的数组来存储平方数组即可。因为这是一个排序的递增序列，所以会有负数，但是数组两边都是值平方的最大值，所以每次比较两边的值，可以得到对应的最大值。value，然后unshift到数组时间复杂度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++}}returnret};875。爱吃香蕉的科科分析——两个点l=1,r=piles[max]，分别代表最大和最小速度；这样找出中间值，然后判断h小时内能不能吃，能吃就向左逼近，不能吃就向右逼近，直到每次出现最小速度mid，必须遍历piles一次，所以时间复杂度为nlognvarminEatingSpeed=function(piles,h){letl=1,r=piles.reduce((prev,cur)=>(prev>=cur?prev:当前),1);while(l<=r){constmid=((r-l)>>1)+l;if(getHours(mid)>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--;}计数++；}返回计数;};
