​ 算法中的双指针，并不一定是指我们平常在 c/c++ 使用的指针类型，更多时候其实是数组的下标等，因为它们也是有标识某个元素的功能，通常我们也就顺其自然地称其为 “指针” ！

​ 常见的双指针有两种形式，一种是对撞指针，一种是快慢指针。

对撞指针

​ 一般用于顺序结构中，也称为左右指针。对撞指针从两端向中间移动。一个指针从最左端开始，另一个从最右端开始，然后逐渐往中间逼近。

​ 对撞指针的终止条件一般是两个指针相遇或者错开（也可能在循环内部找到结果直接跳出循环），也就是：

• left == right（两个指针指向同一位置）
• left > right（两个指针错开）

快慢指针

​ 又称为龟兔赛跑算法，其基本思想就是使用两个移动速度不同的指针在数组或链表等序列结构上移动。这种方法对于处理环形链表或数组非常有用！

​ 其实不单单是环形链表或者是数组，如果我们要研究的问题出现循环往复的情况时，均可考虑使用快慢指针的思想。快慢指针的实现方式有很多种，最常用的一种就是：

• 在一次循环中，每次让慢的指针向后移动一位，而快的指针往后移动两位，实现一快一慢。

283. 移动零

283. 移动零

​ 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

​ 请注意 ，必须在不复制数组的情况下原地对数组进行操作。

示例 1:

输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]

示例 2:

输入: nums = [0]
输出: [0]

提示:

• 1 <= nums.length <= 104
• -231 <= nums[i] <= 231 - 1

解题思路

​ 其实这道题就是将**【数组进行分块】**的题型，这种类型的题，经常使用双指针来解决！比如这道题，要求我们将 0 移动到末尾，其实本质就是将数组划分为非零和零的两个分块！

算法思路

​ 我们可以使用双指针来解决，其中用一个 cur 指针来遍历整个数组，另一个 dest 指针用来指向非零序列的最后一个位置。

​ 然后根据 cur 的遍历途中遇到的情况，分类处理，实现数组的划分！在 cur 遍历途中，使得 [0, dest] 的元素全部都是非零元素，而 [dest+1, cur-1] 区间的元素都是零，剩下的 [cur, n - 1] 则是未处理的部分！

算法流程

1. 首先初始化 cur = 0（用来遍历数组），初始化 dest = -1（指向非零序列的最后一个位置，因为刚开始还不存在，所以我们规定其从 -1 开始！）
2. cur 依次往后遍历每个元素，遍历到的元素会有以下两种情况：
   • 若 nums[cur] == 0，则 cur 直接 ++。
     • 因为我们的目标是要让 [dest+1, cur-1] 区间的元素都为零，所以让 cur 直接向后走，那么当前位置就变成了 cur-1 了，那么不就达到要求落在 [dest+1, cur-1] 区间内了对不对！
   • 若 nums[cur] != 0，则 dest++，并且交换 nums[cur] 和 nums[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) 
    {
        int n = nums.size();
        int dest = -1, cur = 0; // 初始化
        while(cur < n)
        {
            if(nums[cur] != 0)
            {
                dest++;
                swap(nums[cur], nums[dest]);
            }
            cur++;
        }
    }
};