双指针的用法
双指针是处理数组和链表问题的利器，常见的有两种形式：对撞指针和快慢指针。
对撞指针 通常用于顺序结构。两个指针分别从两端向中间移动，一个从最左端开始，另一个从最右端开始，逐渐逼近。终止条件一般是两个指针相遇或错开（例如 left == right 或 left > right），也可能是在循环内部找到结果直接跳出。
快慢指针 又称龟兔赛跑算法，基本思想是使用两个移动速度不同的指针在序列上移动。这种方法特别适合处理环形链表或存在循环往复逻辑的问题。 实现方式中，最常用的是在一次循环中，让慢指针每次向后移动一位，而快指针每次移动两位，实现一快一慢的节奏。
相关题解
1. 移动零
这类题目核心在于【数组分两块】，即根据某种规则将数组内容划分为左右两部分。使用双指针可以高效完成原地划分。
思路解析 我们可以用一个 cur 指针遍历整个数组，另一个 dest 指针记录将要排的非零数序列位置。在 cur 遍历期间，保证 [0, dest-1] 的元素全部是非零元素，[dest, cur-1] 的元素全是零。
流程步骤
- 初始化 cur=0，dest=-1。
- cur 依次往后遍历每个元素：
- 若遇到 0，cur 直接++。因为目标是让 [dest, cur-1] 内的元素全为 0。
- 若遇到非 0 元素，交换 cur 位置和 dest+1 位置的元素，之后让 dest++、cur++。 这样能确保 [0, dest-1] 始终是非零区间。
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int dest = -1;
for (int cur = 0; cur < nums.size(); ++cur) {
if (nums[cur] != 0) {
swap(nums[++dest], nums[cur]);
}
}
}
};
这个方法其实是快速排序中【数据划分】的重要一步。若将快排拆解，这一段小代码就是实现快排的核心步骤。
2. 复写零
如果从前向后原地复写，由于 0 的出现会占用额外空间，导致后面的数被覆盖。因此选择从后往前复写。
思路解析 分为两步：先找到最后一个需要复写的数的位置，然后从后向前进行复写操作。
流程步骤
- 初始化 cur=0，dest=-1。
- 寻找终点：当 cur < n 时，判断 cur 位置元素。若为 0，dest 往后移两位；否则移一位。直到 dest 到达结束位置或越界。
- 若 dest 越界到 n 的位置，说明最后一个 0 被截断，需特殊处理：将 n-1 位置设为 0，cur 前移，dest 前移两位。
- 从 cur 位置开始往前遍历，还原复写后的结果。
class Solution {
public:
{
n = arr.();
dest = , cur = ;
(cur < n) {
(arr[cur] == ) dest += ;
dest++;
(dest >= n) ;
cur++;
}
(dest == n && arr[cur] == ) {
arr[n - ] = ;
cur--;
dest -= ;
} {
dest--;
}
(cur >= ) {
(arr[cur] == ) {
arr[dest--] = ;
arr[dest--] = ;
} {
arr[dest--] = arr[cur];
}
cur--;
}
}
};
