《算法闯关指南：优选算法-双指针》--01移动零，02复写零

LOTSO

发布于 2025-10-29 14:53:26

8900

文章被收录于专栏：C++C++

运行总次数：0

🔥个人主页：@草莓熊Lotso 🎬作者简介：C++研发方向学习者 📖个人专栏：《C++知识分享》《Linux 入门到实践：零基础也能懂》《数据结构与算法》《测试开发实战指南》《算法题闯关指南》 ⭐️人生格言：生活是默默的坚持，毅力是永久的享受。

前言：聚焦算法题实战，系统讲解三大核心板块：优选算法：剖析动态规划、二分法等高效策略，学会寻找“最优解”。递归与回溯：掌握问题分解与状态回退，攻克组合、排列等难题。贪心算法：理解“局部最优”到“全局最优”的思路，解决区间调度等问题内容以题带点，讲解思路与代码实现，帮助大家快速提升代码能力

双指针算法介绍：

常见的双指针有两种形式，一种对撞指针，一种是左右指针。

对撞指针：

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

对撞指针从两端向中间移动。一个指针从最左端开始，另一个从最右端开始，然后逐渐往中间逼近。
对撞指针的终止条件一般是两个指针相遇或者错开（也可能在循环内部找到结构直接跳出循环），也就是：left==right（两个指针指向同一个位置），left>right（两个指针错开）

快慢指针：

又称龟兔赛跑算法，其基本思想就是使用两个移动速度不同的指针在数组或链表等序列结构上移动。

这种方法对于处理环形链表或数组非常有用。其实不单单是环形链表或者数组，如果我们要研究的问题出现循环往复的情况时，均可考虑使用快慢指针的思想。

快慢指针的实现方法有很多种，最常用的一种就是：

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

01.移动零

【数组分两块】是非常常见的一种题型，主要就是根据一种划分方式，将数组的内容分成左右两部分。这种类型的题，一般就是使用【双指针】来解决。

题目链接：

283. 移动零 - 力扣（LeetCode）

题目描述：

题目示例：

解法：(快排的思想：数组划分区间-数组分两块)

算法思路：

在本题中，我们可以用一个 cur 指针来扫描整个数组，另一个 dest 指针用来记录非零序列的最后一个位置，根据 cur 在扫描的过程中，遇到的不同情况，分类处理，实现数组的划分。
在 cur 遍历期间，使【0，dest】的元素全部都是非零元素，【dest+1，cur-1】的元素全是零

算法流程：

1.初始化 cur=0（用来遍历数组），dest=-1（指向非零元素序列的最后一个位置。因为刚开始我们不知道最后一个非零元素在什么位置，因此初始化为 -1）

2.cur 依次往后遍历每个元素，遍历到的元素会有下面两种情况：

2.1：遇到的元素是 0 ，cur 直接 ++ 。因为我们的目标是让【dest+1，cur-1】内的元素全都是零，因此当 cur 遇到 0 的时候，直接 ++ ,就可以让 0 在 cur-1 的位置上，从而在【dest+1，cur-1】内；

2.2：遇到的元素不是 0 ，dest++，并且交换 cur 位置和 dest 位置的元素，之后让 cur++，扫描下一个元素。

因为 dest 指向的位置是非零元素区间的最后一个位置，如果扫描到一个新的非零元素，那么他的位置应该在 dest+1 的位置上，因此 dest 先自增 1；
dest++ 之后，指向的元素就是 0 元素（因为非零元素区间末尾的后一个元素就是 0 ），因此可以交换到 cur 所处的位置上，实现 【0，dest】的元素全部都是非零元素，【dest+1，cur-1】的元素全是零。

C++代码演示：

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

算法总结&&笔记展示：

这里用到的方法是我们学习【快排算法】的时候，【数据划分】过程的重要一步。如果将快排算法拆解的话，这一小段代码就是实现快排算法的【核心步骤】。

笔记的字有点丑，大家见谅：

02.复写零

题目链接：

1089. 复写零 - 力扣（LeetCode）

题目描述：

题目示例：

解法：（原地复写-双指针）

算法思路：

如果【从前往后】进行原地复写操作的话，由于 0 的出现会复写两次，导致没有复写的数【被覆盖掉】。因此我们选择【从后往前】的复写策略。
但是【从后往前】复写的时候，我们需要找到【最后一个复写的数】，因此我们的大体流程分两步：1.先找到最后一个复写的数；2.然后从后往前进行复写操作

算法流程：

1.初始化两个指针 cur=0，dest=0；

2.找到最后一个复写的数：

判断 cur 位置的元素：（1）如果是 0 的话，dest 往后移动两位；（2）否则，dest 往后移动一位
判断 dest 这时候是否已经到结束位置，如果结束就终止循环；
如果没有结束，cur++，继续判断。

3.判断 dest 是否越界到 n 的位置：

如果越界，执行下面三步：

n-1 位置的值修改成 0 ；
cur 向前移动一步（cur--）；
dest 向前移动两步（dest -= 2)；

4.从 cur 位置开始往前遍历原数组，依次还原出复写后的结果数组：

4.1 判断 cur 位置的值：

如果是 0 ：dest 以及 dest-1 位置修改成 0 ，dest-=2；
如果非零：dest 位置修改成 0 ，dest -= 1；

4.2 cur--，复写下一个位置。

C++代码演示：

class Solution {
public:
    void duplicateZeros(vector<int>& arr) {
        int cur=0,dest=-1;
        int n=arr.size();
        //找到最后一个复写的数
        while(cur<n)
        {
            if(arr[cur])dest++;
            else dest+=2;
            if(dest>=n-1) break;
            cur++;
        }
        if(dest>=n)
        {
            arr[n-1]=0;
            dest-=2;
            cur--;
        }
        while(cur>=0)
        {
            if(arr[cur])
            {
                arr[dest--]=arr[cur];
            }else{
                arr[dest--]=0;
                arr[dest--]=0;
            }
            cur--;
        }
    }
};