一、双指针算法介绍
双指针是处理序列结构问题时的高频技巧，主要分为对撞指针和快慢指针两种形态。
1. 对撞指针
一般用于顺序结构中，也称左右指针。两个指针分别从两端向中间移动，一个从最左端开始，另一个从最右端开始，逐渐逼近。终止条件通常是两个指针相遇（left == right）或者错开（left > right）。
2. 快慢指针
又称龟兔赛跑算法，基本思想是使用两个移动速度不同的指针在数组或链表等序列结构上移动。这种方法对于处理环形链表或数组非常有用，只要问题出现循环往复的情况，均可考虑使用快慢指针的思想。
最常用的实现方式是在一次循环中，让慢指针每次向后移动一位，而快指针往后移动两位。
01、移动零
题目链接： 283. 移动零 - 力扣（LeetCode）
题目描述： 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
题目示例：
解法思路： 这道题的核心其实借鉴了快速排序中的分区思想。我们可以用一个 cur 指针来扫描整个数组，另一个 dest 指针用来记录非零序列的最后一个位置。根据 cur 在扫描的过程中遇到的不同情况分类处理，实现数组的划分。
在 cur 遍历期间，保证【0, dest】区间的元素全部都是非零元素，【dest+1, cur-1】区间的元素全是零，而 cur 后面的元素则是未处理的。
具体流程：
- 初始化 cur = 0（用来遍历数组），dest = -1（指向非零元素序列的最后一个位置。因为刚开始还没有进行遍历，此时相当于还没有非零元素的序列，因此初始化为 -1）。
- cur 依次往后遍历每个元素，遍历到的元素会有下面两种情况：
- 遇到的元素是 0，cur 直接++，不需要对 dest 进行操作。因为我们的目标是让【dest+1, cur-1】内的元素全都是 0，因此当 cur 遇到 0 的时候，直接++，就可以保证该区间内依然全为 0；
- 遇到的元素不是 0，dest++，并且交换 cur 位置和 dest 位置的元素，之后让 cur++，扫描下一个元素。
这里有个细节：因为 dest 指向的位置是非零元素区间的最后一个位置，如果扫描到一个新的非零元素，那么这个非零元素的位置应该在 dest+1 的位置上，因此 dest 先自增 1。dest++ 之后，指向的元素就是 0 元素（因为非零元素区间末尾的后一个元素就是 0），因此可以交换到 cur 所处的位置上，实现【0, dest】的元素全部都是非零元素。
C++ 代码演示：
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int dest = -1;
int cur = 0;
while(cur != nums.size()) {
// 如果当前元素非零，则将其交换到 dest 的下一个位置
if(nums[cur]) {
swap(nums[++dest], nums[cur]);
}
cur++;
}
}
};
算法总结： 这里用到的方法就是我们在数据结构中学习快排算法的时候，数据划分过程的重要一步。如果将快排算法的递归拆解成单趟的话，这一小段代码就是实现快排单趟的核心步骤。
02、复写零
题目链接： 1089. 复写零 - 力扣（LeetCode）
题目描述： 给定一个固定长度的整数数组 arr，将数组中出现的每个零都复写一遍，并将其余元素向右平移。
题目示例：
解法思路： 如果从前往后进行原地复写操作的话，由于 0 的出现会复写两次，导致没有复写的数被覆盖掉。因此我们选择从后往前的复写策略。
但是从后往前复写的时候，我们需要找到最后一个复写的数，因此大体流程分两步：1. 先找到最后一个复写的数；2. 然后从后往前进行复写操作。
具体流程：
- 初始化两个指针 cur = 0，dest = -1。
- 找到最后一个复写的数：
- 判断 cur 位置的元素：如果是 0 的话，dest 往后移动两位；否则，dest 往后移动一位。
- 判断 dest 这时候是否已经到结束位置，如果结束就终止循环。
- 如果没有结束，cur++，继续判断。
- 判断 dest 是否越界到 n 的位置：
- 如果越界，执行下面三步：n-1 位置的值修改成 0；cur 向前移动一步（cur--）；dest 向前移动两步（dest -= 2）。
- 从 cur 位置开始往前遍历原数组，依次还原出复写后的结果数组：
- 判断 cur 位置的值：如果是 0，dest 以及 dest-1 位置修改成 0，dest-=2；如果非零，dest 位置修改成 0，dest -= 1。
- cur--，复写下一个位置。
C++ 代码演示：
class Solution {
public:
void duplicateZeros(vector<int>& arr) {
// 1. 先找到最后一个复写的数
int dest = -1;
int cur = 0;
while(1) {
dest++;
if(arr[cur] == 0) {
dest++;
}
if(dest >= arr.size() - 1) {
break;
}
cur++;
}
// 2. 处理越界情况
if(dest == arr.size()) {
arr[arr.size() - 1] = 0;
dest -= 2;
cur--;
}
// 3. 从后向前完成复写操作
while(cur >= 0) {
if(arr[cur] == 0) {
arr[dest--] = arr[cur];
}
arr[dest--] = arr[cur--];
}
}
};
算法总结及流程解析： 之所以会出现越界，是因为如果最后一个复写的数为 0，则可能出现复写的位置在下标 n-1 和 n，但下标为 n 就是越界。也就是说实际上并没有复写两遍 0 而只是数组最后一个位置复写为 0。所以如果越界操作就是数组最后位置手动置为 0 后让 dest 回到倒数第二个位置，cur-- 就是让最后一个复写的数变成前一个。
