【双指针】对撞指针 && 快慢指针 && 移动零

双指针介绍

算法中的双指针，并不一定是指我们平常在 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++;
        }
    }
};