《算法题讲解指南：优选算法-双指针》--01移动零，02复写零
🔥小叶-duck：个人主页
❄️个人专栏：《Data-Structure-Learning》
✨未择之路，不须回头
已择之路，纵是荆棘遍野，亦作花海遨游
目录
一、双指针算法介绍
在正式讲解本次的算法题之前我们先来看看算法中一个非常常用的方法——双指针。双指针有两种形式，一种对撞指针，一种是左右指针。
1、对撞指针
一般用于顺序结构中，也称左右指针。
- 对撞指针从两端向中间移动。一个指针从最左端开始，另一个从最右端开始，然后逐渐往中间逼近。
- 对撞指针的终止条件一般是两个指针相遇或者错开（也可能在循环内部找到结构直接跳出循环），也就是：left == right（两个指针指向同一个位置），left > right（两个指针错开）
2、快慢指针
又称龟兔赛跑算法，其基本思想就是使用两个移动速度不同的指针在数组或链表等序列结构上移动。
这种方法对于处理环形链表或数组非常有用。其实不单单是环形链表或者数组，如果我们要研究的问题出现循环往复的情况时，均可考虑使用快慢指针的思想。
快慢指针的实现方法有很多种，最常用的一种就是：
- 在一次循环中，每次让慢的指针向后移动一位，而快的指针往后移动两位，实现一快一慢
01、移动零
题目链接：
283. 移动零 - 力扣（LeetCode）
题目描述：
题目示例：
解法：(快排的思想：数组划分区间-数组分块)
【数组分块】是非常常见的一种算法技巧，主要就是根据一种划分方式，将数组的内容分成左右两部分。这种类型的题，一般就是使用【双指针】来解决。
算法思路：
- 我们可以用一个 cur 指针来扫描整个数组，另一个 dest 指针用来记录非零序列的最后一个位置，根据 cur 在扫描的过程中，遇到的不同情况，分类处理，实现数组的划分。
- 在 cur 遍历期间，保证【0，dest】区间的元素全部都是非零元素，【dest+1，cur-1】区间的元素全是零，而 cur 后面的元素则是未处理的。
算法流程：
1、初始化 cur = 0（用来遍历数组），dest = -1（指向非零元素序列的最后一个位置。因为刚开始还没有进行遍历，此时相当于还没有非零元素的序列，因此初始化为 -1）
2.cur 依次往后遍历每个元素，遍历到的元素会有下面两种情况：
2.1 遇到的元素是 0 ，cur直接++ ，不需要对 dest 进行操作。因为我们的目标是让【dest+1，cur-1】内的元素全都是0，因此当 cur 遇到 0 的时候，直接 ++ ,就可以保证【dest+1，cur-1】这个区间内依然全为0；
2.2 遇到的元素不是 0 ，dest++，并且交换 cur 位置和 dest 位置的元素，之后让 cur++，扫描下一个元素。
- 因为 dest 指向的位置是非零元素区间的最后一个位置，如果扫描到一个新的非零元素，那么这个非零元素的位置应该在 dest+1 的位置上，因此 dest 先自增 1；
- dest++ 之后，指向的元素就是 0 元素（因为非零元素区间末尾的后一个元素(下标为 dest+1)就是 0 ），因此可以交换到 cur 所处的位置上，实现【0，dest】的元素全部都是非零元素，【dest+1，cur-1】的元素全是零。
C++ 代码演示：
class Solution { public: void moveZeroes(vector<int>& nums) { int dest = -1; int cur = 0; while(cur != nums.size()) { // if(nums[cur] == 0) // { // cur++; // } // else // { // swap(nums[++dest], nums[cur++]); // } //代码优化 if(nums[cur])//if判断为假则说明cur遇到0 { swap(nums[++dest], nums[cur]); } cur++; } } };算法总结：
这里用到的方法就是我们在数据结构中学习 【快排算法】的时候，【数据划分】过程的重要一步。如果将快排算法的递归拆解成单趟的话，这一小段代码就是实现快排单趟的【核心步骤】。
02、复写零
题目链接：
1089. 复写零 - 力扣（LeetCode）
题目描述：
题目示例：
解法：（原地复写——双指针）
算法思路：
- 如果【从前往后】进行原地复写操作的话，由于 0 的出现会复写两次，导致没有复写的数【被覆盖掉】。因此我们选择【从后往前】的复写策略。
- 但是 【从后往前】复写的时候，我们需要找到 【最后一个复写的数】，因此我们的大体流程分两步：1.先找到最后一个复写的数；2.然后从后往前进行复写操作
算法流程：
1.初始化两个指针 cur = 0，dest = -1；
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) { // 1. 先找到最后⼀个复写的数 int dest = -1; int cur = 0; while(1) { dest++; if(arr[cur] == 0) { dest++; } if(dest >= arr.size() - 1) { break; } cur++; } // 2. 处理越界情况 if(dest == arr.size()) { arr[arr.size() - 1] = 0; dest -= 2; cur--; }//之所以会越界是因为如果最后一个复写的数为0 //则可能出现复写的位置在下标n-1和n，但下标为n就是越界 //也就是说实际上并没有复写两遍0而只是数组最后一个位置复写为0 //所以如果越界操作就是数组最后位置手动置为0后让dest回到倒数第二个位置 //cur--就是让最后一个复写的数变成前一个 // 3. 从后向前完成复写操作 while(cur >= 0) { if(arr[cur] == 0) { arr[dest--] = arr[cur]; } arr[dest--] = arr[cur--]; } } };算法总结及流程解析：
结束语
到此，本次的算法题就讲解完了，这是小萌新讲解算法题的开始，后面我会不断地对非常经典且精选的算法题为大家进行讲解，希望大家能有所收获！
