算法魅力-双指针的实战
目录
1.双指针的介绍
1. 左右指针（对撞指针）
2. 快慢指针
2.题目练习讲解
2.1 移动零
算法思路
代码展示
画图效果效果
2.2 复写零
算法思路
代码展示
2.3 快乐数
算法思路
代码展示
2.4 盛最多水的容器
算法思路
代码展示
结束语
1.双指针的介绍
双指针算法是一种常用的算法技巧，通常用于解决数组或链表相关的题目。双指针算法的核心思想是使用两个指针在数组或链表上移动，这里的指针并不是只是指指针，我们可以用数组下标来代替，以达到解决问题的目的。根据具体问题，双指针可以分为以下几种类型：
1. 左右指针（对撞指针）
左右指针通常用于处理数组中的问题，其中一个指针从数组的开始位置向后移动，另一个指针从数组的结束位置向前移动。
left == right （两个指针指向同一个位置）left > right （两个指针错开）
典型问题：
二分查找：在有序数组中查找一个特定的元素。
两数之和：在数组中找到两个数，使它们的和等于一个给定的数。
2. 快慢指针
快慢指针主要用于处理链表中的问题，两个指针从同一位置出发，一个指针（快指针）每次移动两个节点，另一个指针（慢指针）每次移动一个节点。
典型问题：
判断链表中是否有环：Floyd 判圈算法（龟兔赛跑算法）。
找到链表的中间节点：快指针到达终点时，慢指针正好在中间。
双指针算法的关键在于指针的移动策略和终点的判断条件，根据具体问题，双指针的移动策略和判断条件可能会有所不同。
2.题目练习讲解
2.1 移动零
283. 移动零 - 力扣（LeetCode）
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意 ，必须在不复制数组的情况下原地对数组进行操作。
示例 1:
输入: nums = [0,1,0,3,12]输出: [1,3,12,0,0]
示例 2:
输入: nums = [0]输出: [0]
算法思路
cur 依次往后遍历每个元素，遍历到的元素会有下面两种情况：i. 遇到的元素是 0 ， cur 直接 ++ 。因为我们的目标是让 [dest + 1, cur - 1] 内的元素全都是零，因此当 cur 遇到 0 的时候，直接 ++ ，就可以让 0 在 cur - 1的位置上，从而在 [dest + 1, cur - 1] 内；ii. 遇到的元素不是 0 ， dest++ ，并且交换 cur 位置和 dest 位置的元素，之后让cur++ ，扫描下⼀个元素。• 因为 dest 指向的位置是非零元素区间的最后一个位置，如果扫描到一个新的非零元素，那么它的位置应该在 dest + 1 的位置上，因此 dest 先自增 1 ；• dest++ 之后，指向的元素就是 0 元素（因为非零元素区间末尾的后一个元素就是0 ），因此可以交换到 cur 所处的位置上，实现 [0, dest] 的元素全部都是非零元素， [dest + 1, cur - 1] 的元素全是零。
代码展示
class Solution
{
public:void moveZeroes(vector<int>& nums) {for(int cur = 0, dest = -1; cur < nums.size(); cur++)if(nums[cur]) // 处理⾮零元素swap(nums[++dest], nums[cur]);}
};当然，我们也可以让dest指向首元素，后续算法逻辑类似，只是变成了先交换在++。
class Solution
{
public:void moveZeroes(vector<int>& nums) {for(int cur = 0, dest = 0; cur < nums.size(); cur++)if(nums[cur]) // 处理⾮零元素swap(nums[dest++], nums[cur]);}
};画图效果效果
2.2 复写零
1089. 复写零 - 力扣（LeetCode）
算法思路
同样这道题我们用双指针的算法，我们首先普遍会想到定义两个指针，从前向后开始复写，从首元素开始移动，在移动过程中由于0会写两次，我们会发现后一个数据会被覆盖就会达不到效果。
故当我们换成从后向前复写时，可以避免这种情况，但是我们需要找到复写的最后一个元素。
我们还是定义两个指针：
初始化两个指针 cur = 0 ， dest = -1 ；b. 找到最后一个复写的数：i. 当 cur < n 的时候，一直执行下面循环：• 判断 cur 位置的元素:◦ 如果是 0 的话， dest 往后移动两位；◦ 否则， dest 往后移动一位。• 判断 dest 时候已经到结束位置，如果结束就终止循环；• 如果没有结束， cur++ ，继续判断。从 cur 位置开始往前遍历原数组，依次还原出复写后的结果数组：i. 判断 cur 位置的值：1. 如果是 0 ： dest 以及 dest - 1 位置修改成 0 ， dest -= 2 ；2. 如果⾮零： dest 位置修改成 0 ， dest -= 1 ；ii. cur-- ，复写下一个位置。
while(cur>=0){if(arr[cur])arr[dest--]=arr[cur--];else{arr[dest--]=0;arr[dest--]=0;cur--;}
}我们发现有些情况会数组越界，超出一位，当我们往前遍历复写的时候就会出现问题，因为数组外赋值了。
所以我们要处理数组越界的情况
代码展示
class Solution {
public:void duplicateZeros(vector<int>& arr) {int cur=0,dest=-1;int n=arr.size();while(cur<n){if(arr[cur])dest++;elsedest+=2;if(dest>=n-1)break;cur++;}if(dest==n){arr[n-1]=0;dest-=2;cur--;}while(cur>=0){if(arr[cur])arr[dest--]=arr[cur--];else{arr[dest--]=0;arr[dest--]=0;cur--;}}}
};图片效果展示
2.3 快乐数
202. 快乐数 - 力扣（LeetCode）
算法思路
首先可以将题目解答猜成两部分，第一部分是求取每个位数上的平方和，第二步就是与1进行比较。
通过快乐数的定义我们发现其实当它结果为1时，也会陷入一个1的循环。所以不管那种过程，累加次都会陷入循环，最终都会走到一个环中进行循环。
简单证明一下：
代码展示
class Solution {
public:int ret(int n){int sum=0;while(n){int a=n%10;sum+=a*a;n=n/10;}return sum;}bool isHappy(int n) {int slow=n;int fast=ret(n);while(slow!=fast){slow=ret(slow);fast=ret(ret(fast));}return slow==1;}
};2.4 盛最多水的容器
11. 盛最多水的容器 - 力扣（LeetCode）
这道题我们首先会想到枚举，通过暴力的解法将每一种的体积算出来，选出最大的。
lass Solution {
public:int maxArea(vector<int>& height) {int n=height.size();int ret=0;for(int i=0;i<n;i++){for(int j=i+1;j<n;j++){ret = max(ret, min(height[i], height[j]) * (j - i));}}return ret;}
};但是这种解法会超时。所以需要换一种思路。我们可以采用对撞指针的思路。
算法思路
代码展示
class Solution {
public:int maxArea(vector<int>& height) {int left=0,right=height.size()-1;int max=0;for(int i=0;i<height.size();i++){if(max<((right-left)*min(height[left],height[right])))max=(right-left)*min(height[left],height[right]);if(height[left]<=height[right])left++;elseright--;}return max;}
};结束语
相信通过本篇博客大家对双指针算法有了一定的了解，下篇博客我们将继续讲解三道例题加深对双指针的印象。
最后感谢各位友友的支持，有不同的解法思路欢迎大家在评论区讨论！！！