【算法篇】初识双指针

作者主页

欢迎收看双指针算法

目录/索引：

目录

欢迎收看双指针算法

双指针的简介：

题目一：移动零

题目链接：

题目解析：

时间复杂度的分析：

解法一：暴力枚举

解法二： 双指针

代码的编写：

提交代码：

题目二： 复写零

题目链接：

题目解析：

代码的编写：

运行结果：

​编辑题目三： 快乐数

题目链接：

题目解析：

代码编写：

运行结果：

双指针的简介：

常见的双指针有两种形式：**对撞指针** 和 **快慢指针**。

一、对撞指针 对撞指针一般用于顺序结构中，也称**左右指针**。

- 对撞指针从两端向中间移动：一个指针从最左端开始，另一个从最右端开始，然后逐渐往中间逼近。

- 对撞指针的终止条件一般是两个指针相遇或者错开（也可能在循环内部找到结果直接跳出循环），即： 1. left == right（两个指针指向同一个位置） 2. left > right（两个指针错开）

二、快慢指针 快慢指针又称为**龟兔赛跑算法**，其基本思想是使用两个移动速度不同的指针，在数组或链表等序列结构上移动。 - 这种方法对于处理环形链表或数组非常有用。 - 不单单是环形链表或数组，研究的问题出现循环往复的情况时，均可考虑使用快慢指针的思想。 - 最常用的实现方式：在一次循环中，每次让慢的指针向后移动一位，而快的指针往后移动两位，实现一快一慢。

题目一：移动零

题目链接：

移动零

题目解析：

由题意得： 就是存在一个数组，我们要把这个数组的所有的元素进行移动到数组的末尾。

示例分析：

时间复杂度的分析：

解法一：暴力枚举

由图一变为图二：

首先遇到这种情况我们一般都会进行暴力枚举的。

如果暴力枚举的话我们会先进行一次for如果这个位置为“0”那就在这个位置的基础上再次进行for不为0的话。

for(int i=0; i < nums.size() ; i++) { if(nums[i]==0) { for(int j=i ; 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就可以完成这样的操作了。

图解：

时间复杂度： 相当于我们两个指针都只遍历了一遍数组。所以我们的时间复杂度是O（1）。

算法的正确性： 我们对于每个元素都进行了查询并且我么的。

代码的编写：

class Solution { public: void moveZeroes(vector<int>& nums) { int left=0; int right=0; while(right<nums.size()) { if(nums[right]!=0) swap(nums[left++],nums[right]); right++; } } };

提交代码：

题目二： 复写零

题目链接：

复写零

题目解析：

有题意得： 我们的数组的长度是固定的， 我们每一次的遇到0的时候就要将这个零再次的进行写一边， 如果到了最后数组越界了，那么数组后面的值，直接不要了。 数组的小是固定的。

方法选择：

所以两个指针定义在前面是不行的。 但是我们除啦把指针定义在前面还可以把指针定义在后面， 但是像我们下图的测试用例来说我们后面的5是没有在最终的数组进行体现的。 所以我们可以先初始化一个计数器， 来初步的计算一下我们最总索要遍历到那个位置。

代码的编写：

class Solution { public: void duplicateZeros(vector<int>& arr) { int slow=0; int fast=-1; int n=arr.size(); while(slow<n)//测试我们前面的数组最多运行到哪里了 { if(arr[slow]==0)fast+=2;//遇到0就+=2 否则++ else fast++; if(fast>=n-1) break; slow++; } if(fast==n)//我们越界了最后一个slow一定停在0上，我们的fast到n了。越界了。所以我们将最后一个数组的元素置为0。 { arr[n-1]=0; slow--; fast-=2; } while(slow>=0) { if(arr[slow]==0) { arr[fast--]=0; arr[fast--]=0; slow--; } else { arr[fast--]=arr[slow--]; } } } };

运行结果：

题目三： 快乐数

题目链接：

快乐数

题目解析：

给我们一个正整数，每一次将我们的数子拆分下来进行平方，得到的数继续进行平方， 直到这个数为1，就是快乐数。

当然这里的结束条件有两种： 1.最后循环变成了1。

到那时为1时它自身也成环了。

2、循环后自身变成了一个链式结构。

这样我们就知道了它们都成环但是快乐数的环他是同一个数的循环，而我们非快乐数的环是不同数据成环，所以我们可以使用快慢指针来解决这个问题（快慢指针是否正确呢）。等到这两个数都进入环里的时候看fast和slow相遇的时候两者的值是否等于1就可以了。（那么为什么他们一定相遇呢？？？）这里我们先记住结论不论是slow（1）：fast（2） 是 1：3, 1：4...他们都会进行相遇的。 在后面的文章会给大家深度的证明一下的。

代码编写：

class Solution { public: int Sum(int n) { int sum=0; while(n>0) { int t= n%10; n/=10; sum += t*t; } return sum; } bool isHappy(int n) { int slow=n; int fast=Sum(n); while(slow != fast) { slow=Sum(slow); fast=Sum(Sum(fast)); } return slow==1; } };

运行结果：