作者主页作者简要描述算法篇Linux篇QT百日筑基篇数据结构篇欢迎收看双指针算法目录/索引目录欢迎收看双指针算法双指针的简介题目一移动零题目链接题目解析时间复杂度的分析解法一暴力枚举解法二 双指针代码的编写提交代码题目二 复写零题目链接题目解析代码的编写运行结果​编辑题目三 快乐数题目链接题目解析代码编写运行结果双指针的简介常见的双指针有两种形式**对撞指针** 和 **快慢指针**。一、对撞指针 对撞指针一般用于顺序结构中也称**左右指针**。- 对撞指针从两端向中间移动一个指针从最左端开始另一个从最右端开始然后逐渐往中间逼近。- 对撞指针的终止条件一般是两个指针相遇或者错开也可能在循环内部找到结果直接跳出循环即 1. left right两个指针指向同一个位置 2. left right两个指针错开二、快慢指针 快慢指针又称为**龟兔赛跑算法**其基本思想是使用两个移动速度不同的指针在数组或链表等序列结构上移动。 - 这种方法对于处理环形链表或数组非常有用。 - 不单单是环形链表或数组研究的问题出现循环往复的情况时均可考虑使用快慢指针的思想。 - 最常用的实现方式在一次循环中每次让慢的指针向后移动一位而快的指针往后移动两位实现一快一慢。题目一移动零题目链接移动零题目解析由题意得 就是存在一个数组我们要把这个数组的所有的元素进行移动到数组的末尾。示例分析时间复杂度的分析解法一暴力枚举由图一变为图二首先遇到这种情况我们一般都会进行暴力枚举的。如果暴力枚举的话我们会先进行一次for如果这个位置为“0”那就在这个位置的基础上再次进行for不为0的话。for(int i0; i nums.size() ; i) { if(nums[i]0) { for(int ji ; j nums.size();j) { if(nums[j]!0) { swap(nums[i], nums[j]); break(); } } } }当然这样搞的话也能做出来但是我们分析一下在极限情况下它的时间复杂度为O(n*n)。极端情况[0,0,0,0,1,1,1,1];显然我们还有更优解那就是我们本篇涉及的双指针。解法二 双指针解法说明我们定义连个指针一个left 一个right来进行对这两个指针的操作我们可以让我们的left每次走一步直接停下 right遇到0直接跳过遇到0 我们直接停下。那么在进行swap就可以完成这样的操作了。图解时间复杂度 相当于我们两个指针都只遍历了一遍数组。所以我们的时间复杂度是O1。算法的正确性 我们对于每个元素都进行了查询并且我么的。代码的编写class Solution { public: void moveZeroes(vectorint nums) { int left0; int right0; while(rightnums.size()) { if(nums[right]!0) swap(nums[left],nums[right]); right; } } };提交代码题目二 复写零题目链接复写零题目解析有题意得 我们的数组的长度是固定的 我们每一次的遇到0的时候就要将这个零再次的进行写一边 如果到了最后数组越界了那么数组后面的值直接不要了。 数组的小是固定的。方法选择所以两个指针定义在前面是不行的。 但是我们除啦把指针定义在前面还可以把指针定义在后面 但是像我们下图的测试用例来说我们后面的5是没有在最终的数组进行体现的。 所以我们可以先初始化一个计数器 来初步的计算一下我们最总索要遍历到那个位置。代码的编写class Solution { public: void duplicateZeros(vectorint arr) { int slow0; int fast-1; int narr.size(); while(slown)//测试我们前面的数组最多运行到哪里了 { if(arr[slow]0)fast2;//遇到0就2 否则 else fast; if(fastn-1) break; slow; } if(fastn)//我们越界了最后一个slow一定停在0上我们的fast到n了。越界了。所以我们将最后一个数组的元素置为0。 { arr[n-1]0; slow--; fast-2; } while(slow0) { if(arr[slow]0) { arr[fast--]0; arr[fast--]0; slow--; } else { arr[fast--]arr[slow--]; } } } };运行结果题目三 快乐数题目链接快乐数题目解析给我们一个正整数每一次将我们的数子拆分下来进行平方得到的数继续进行平方 直到这个数为1就是快乐数。当然这里的结束条件有两种 1.最后循环变成了1。到那时为1时它自身也成环了。2、循环后自身变成了一个链式结构。这样我们就知道了它们都成环但是快乐数的环他是同一个数的循环而我们非快乐数的环是不同数据成环所以我们可以使用快慢指针来解决这个问题快慢指针是否正确呢。等到这两个数都进入环里的时候看fast和slow相遇的时候两者的值是否等于1就可以了。那么为什么他们一定相遇呢这里我们先记住结论不论是slow1fast2 是 13, 14...他们都会进行相遇的。 在后面的文章会给大家深度的证明一下的。代码编写class Solution { public: int Sum(int n) { int sum0; while(n0) { int t n%10; n/10; sum t*t; } return sum; } bool isHappy(int n) { int slown; int fastSum(n); while(slow ! fast) { slowSum(slow); fastSum(Sum(fast)); } return slow1; } };运行结果