双指针算法初阶详解：移动零与复写零

双指针算法简介

双指针算法是算法题中常见的一种技巧，主要分为对撞指针和快慢指针。

对撞指针

一般用于顺序结构，也叫左右指针。

实现思路：

1. 对撞指针从序列两端向中间移动。
2. 终止条件一般为两个指针相遇或错开。

快慢指针

又称龟兔赛跑算法，使用两个移动速度不同的指针在序列上移动，常用于环形链表或数组。

实现思路：

1. 研究问题是否存在循环往复现象。
2. 设置快指针和慢指针，例如快指针移动两步，慢指针移动一步。

相关例题

移动零

题目描述

给定一个数组 nums，编写一个函数将所有 0 移动到数组末尾，同时保持非零元素的相对顺序。必须在不复制数组的情况下原地对数组进行操作。

示例 1:

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

示例 2:

cpp
输入：nums = [0]
输出：[0]

提示:

• 1 <= nums.length <= 10^4
• -2^31 <= nums[i] <= 2^31 - 1

进阶： 尽量减少完成的操作次数。

实现思路

本质是将非零数放在数组开头且顺序不变，零放在尾端。标准的双指针解法如下：

1. 初始化两个指针 cur 用于扫描数组，dest 用于记录非零序列的最后一个位置。
2. 遍历时 [0, dest] 的元素为非零元素，[dest - 1, cur - 1] 的元素为零元素。
3. 若遇到非零数，则 ++dest 并交换 cur 位置和 dest 位置。

实现代码:

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int n = nums.size();
        int index = -1;
        for (int i = 0; i < n; ++i) {
            if (nums[i]) {
                swap(nums[++index], nums[i]);
            }
        }
    }
};

复写零

题目描述

给你一个长度固定的整数数组 arr，将该数组中出现的每个零都复写一遍，并将其余元素向右平移。注意不要超过该数组长度的位置写入元素。请就地修改，不返回任何东西。

示例 1:

cpp
输入：arr = [1,0,2,3,0,4,5,0]
输出：[1,0,0,2,3,0,0,4]

示例 2:

cpp
输入：arr = [1,2,3]
输出：[1,2,3]

提示:

• 1 <= arr.length <= 10^4
• 0 <= arr[i] <= 9

实现思路

需要判断特殊情况，找到复写后数组的最后一个元素复写前的下标。

1. 使用双指针遍历，确定最后一个可复写的值的位置。
2. 根据是否越界决定是从前往后还是从后往前填充。
3. 从后往前遍历数组进行复写操作，遇到零则写入两个零。

实现代码:

class Solution {
public:
    void duplicateZeros(vector<int>& arr) {
        int cur = 0, dest = -1, s = arr.size();
        while (cur < s) {
            if (arr[cur]) dest++;
            else dest += 2;
            if (dest >= s - 1) break;
            cur++;
        }
        if (dest == s) {
            arr[s - 1] = 0;
            dest -= 2;
            cur--;
        }
        while (cur >= 0) {
            if (arr[cur]) arr[dest--] = arr[cur--];
            else {
                arr[dest--] = 0;
                arr[dest--] = 0;
                cur--;
            }
        }
    }
};