目录
1.双指针的介绍
双指针算法是一种常用的算法技巧，通常用于解决数组或链表相关的题目。双指针算法的核心思想是使用两个指针在数组或链表上移动，这里的指针并不是只是指指针，我们可以用数组下标来代替，以达到解决问题的目的。根据具体问题，双指针可以分为以下几种类型：
1. 左右指针（对撞指针）
左右指针通常用于处理数组中的问题，其中一个指针从数组的开始位置向后移动，另一个指针从数组的结束位置向前移动。
指针从两端向中间移动。一个指针从最左端开始，另一个从最右端开始，然后逐渐往中间逼 近。 对撞指针的 终止条件一般是两个指针相遇或者错开（也可能在循环内部找到结果直接跳出循环），也就是：left == right （两个指针指向同一个位置） left > right （两个指针错开）
典型问题：
二分查找：在有序数组中查找一个特定的元素。
两数之和：在数组中找到两个数，使它们的和等于一个给定的数。
2. 快慢指针
快慢指针主要用于处理链表中的问题，两个指针从同一位置出发，一个指针（快指针）每次移动两个节点，另一个指针（慢指针）每次移动一个节点。
典型问题：
判断链表中是否有环：Floyd 判圈算法（龟兔赛跑算法）。
找到链表的中间节点：快指针到达终点时，慢指针正好在中间。
双指针算法的关键在于指针的移动策略和终点的判断条件，根据具体问题，双指针的移动策略和判断条件可能会有所不同。
2.题目练习讲解
2.1 移动零
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意 ，必须在不复制数组的情况下原地对数组进行操作。
示例 1:
输入: nums = [0,1,0,3,12] 输出: [1,3,12,0,0]
示例 2:
输入: nums = [0] 输出: [0]
算法思路
在本题中，我们可以用一个 cur 指针来扫描整个数组，另一个 dest 指针用来记录非零数序列 的最后一个位置。根据 cur 在扫描的过程中，遇到的不同情况，分类处理，实现数组的划分。 在 cur 遍历期间，使 [0, dest] 的元素全部都是非零元素， [dest + 1, cur - 1] 的元素全是零。 [cur,n-1]是待处理的元素。 首先，我们，我们让dest指向-1的位置，cur指向数组的首元素，通过循环控制cur的移动，无论cur指向谁，一次循环过后都要++，而当cur指向的数据是非0元素时，我们就让dest++,让加之后的dest与cur进行元素交换。 详细就是：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 复写零
算法思路
同样这道题我们用双指针的算法，我们首先普遍会想到定义两个指针，从前向后开始复写，从首元素开始移动，在移动过程中由于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--;
}
}我们发现有些情况会数组越界，超出一位，当我们往前遍历复写的时候就会出现问题，因为数组外赋值了。
所以我们要处理数组越界的情况
如果越界，n - 1 位置的值修改成 0 ； cur 向移动一步； dest 向前移动两步。代码展示
class Solution {
public:
void duplicateZeros(vector<int>& arr) {
int cur=0,dest=-1;
int n=arr.size();
while(cur<n){
if(arr[cur])
dest++;
else
dest+=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 快乐数
算法思路
首先可以将题目解答猜成两部分，第一部分是求取每个位数上的平方和，第二步就是与1进行比较。
通过快乐数的定义我们发现其实当它结果为1时，也会陷入一个1的循环。所以不管那种过程，累加次都会陷入循环，最终都会走到一个环中进行循环。
情况一：一直在 1 中死循环，即 1 -> 1 -> 1 -> 1...... 情况二：在历史的数据中死循环，但始终变不到 1
简单证明一下：
经过一次变化之后的最大值 9^2 * 10 = 810 ( 2^31-1=2147483647 。选一个更大的最 大 9999999999 )，也就是变化的区间在 [1, 810] 之间； 根据「鸽巢原理」，一个数变化 811 次之后，必然会形成一个循环； 因此，变化的过程最终会走到一个圈里面，因此可以用「快慢指针」来解决 将「对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和」这一个 操作记为 x 操作 根据上述分析，我们可以知道，当重复执行 x 的时候，数据会陷入到一个「循环」之中。 而「快慢指针」有一个特性，就是在一个圆圈中，快指针总是会追上慢指针的，也就是说他们总会 相遇在一个位置上。如果相遇位置的值是 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 盛最多水的容器
这道题我们首先会想到枚举，通过暴力的解法将每一种的体积算出来，选出最大的。
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;
}
};但是这种解法会超时。所以需要换一种思路。我们可以采用对撞指针的思路。
算法思路
设两个指针 left ， right 分别指向容器的左右两个端点，此时容器的容积 : v = (right - left) * min( height[right], height[left]) 容器的左边界为 height[left] ，右边界为 height[right] 。 我们假设「左边边界」小于「右边边界」。 如果此时我们固定一个边界，改变另一个边界，水的容积会有如下变化形式： 容器的宽度一定变小。 由于左边界较小，决定了水的高度。 如果改变左边界，新的水面高度度不确定，但是一定不会超过右边的柱子高度，因此容器的容积可能会增大。 ◦ 如果改变右边界，无论右边界移动到哪里， 新的水面的高度一定不会超过左边界，也就是不会超过现在的水面高度，但是由于容器的宽度减小，因此容器的容器一定会变小的。 由此可见，左边界和其余边界的组合情况都可以舍去。所以我们可以 left++ 跳过这个边界，继续去判断下一个左右边界。代码展示
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++;
else
right--;
}
return max;
}
};结束语
标签：实战,cur,dest,元素,++,int,算法,指针 From： https://blog.csdn.net/2302_79376097/article/details/142994454相信通过本篇博客大家对双指针算法有了一定的了解，下篇博客我们将继续讲解三道例题加深对双指针的印象。
最后感谢各位友友的支持，有不同的解法思路欢迎大家在评论区讨论！！！