双指针算法的妙用：提高代码效率的秘密（1）
前言：
从今天开始，小编将陆续分享一些算法题的解题思路和实现过程。为了提升未来的发展空间，也希望通过算法练习来增强自身能力。话不多说，下面进入算法时间！
目录
1.移动零
1.1.题目展示
1.2.题目解答
1.3.题目思路讲解
1.4.代码实现
2.复写零
1.1.题目展示
1.2.题目解答
1.3.题目思路讲解
1.4.代码实现
3.总结
正文：
1.移动零
1.1.题目展示
在题目讲解之前，先各位展示题目来源：283. 移动零 - 力扣（LeetCode）
1.2.题目解答
在讲解题目的思路之前，小编先讲述一下这个题目的意思是什么，阅读此题，我们可以知道这个题目是想要我们把所有的0移动到后面，并且让我们不要去改变非零元素的相当位置，就拿示例一举例，此时非零元素的相对顺序是1,3,12.这就代表着我们把0移动到后面以后，同样也要保证此时的改变后的数组中的顺序是1,3,12开头的，并不能是1,12,3开头的，这个点一定要记住，不然后续做题目的时候包出错的，并且这个题目不让我们去复制数组，这就代表着我们必须是在原始数组上做出移动零操作的，这便是题目传给我们的内容，下面小编讲述这个题目ed做题方法。
1.3.题目思路讲解
下面小编先开始题目思路的讲解，这个题目采取的思想是数组分组的思想，简单来说就是把一个完整的数组分为多个小的数组进行题目的解答，就比如下图这样：
如上图一样，数组分块只不过是把数组分成好几块来着，下面我们就来说一下这个题目的解题方法：双指针法，可能很多读者朋友知道这个解法，因为这个解法常常出现在许多算法题中，当然我知道很多读者朋友会闻指针色变，因为指针这个玩意真的会让人很头疼，小编也曾出过很多篇博客来重点去讲述指针这个大头，不过这个双指针法并不是代表着我们需要去使用指针来进行解题，这个仅仅就是一个思想，此时这个题目我们可以去使用数组下标来近似替代指针，下面开始这个做题方法的讲解。
首先，我们先设置好两个数组下标，分别叫ctr（遍历指针）和dest（目的指针）我们是需要先知道这两个指针的作用，如下图所示：
此时其实就已经把一个完整的数组分块了，分别是【0，dest】：代表着非零元素所在的区间；【dest + 1，cur - 1】代表着零元素所在的区间；【cur，n-1】代表着还没遍历到的区间。这便就是数组的分块，首先我们先把dest设置成-1（因为此时并不知道dest在哪，先把他设置成没有意义的），然后我们让cur和0进行比较，倘若cur的值不等于0，那么将它和dest + 1位置的数据进行交换，至于为什么是dest + 1，请看小编上面的图片，此时我清楚的写着dest位置的数据代表着非零元素的最后一个位置，所以我们自然让它下一个也是非0，之后我们让dest和cur统一往后走；倘若此时的cur是0，那么就很简单了，我们仅需让cur继续往后走就可以，直到找到下一个非零位置的数据，在进行上一步操作，直到cur已经越过数组的边界后，此时我们就实现了移动零，把所有零元素放在了后面，这边就是移动零的题目解题思路，下面小编带领各位读者朋友去进行代码的上手，当然，小编推荐各位，先把思路理清楚，然后自己实现一遍代码，之后再和我的去进行比较，下面小编开始进行代码实操。
1.4.代码实现
首先，我们借助这个题目的例题来进行本代码的讲解例子：
之后，本题目的操作自然是要靠循环来实现，循环的条件的开始自然是cur = 0，dest = -1；它的限制条件肯定是cur < 数组空间的大小；然后我们只让cur往后走就好了，因为dest往后走的条件我说过，自然就是此时cur不等于0了，下面小编展示一下这部分代码的书写：
void moveZeroes(vector<int>& nums)
{
for(int cur = 0,dest = -1;cur < nums.size() ; cur++ )
{
}
}之后我们判断此时的cur是否为0，可以知道此时为0，那么就继续往后走，往后走发现，此时cur不等于0，所以让dest + 1的数据和cur的数据进行交换即可，这部分代码也是比较好写的，因为此时它涉及到了if选择语句的书写，由于难度不大，下面小编直接展示代码的书写：
if(nums[cur]) //这就代表这非0元素
std::swap(nums[++dest],nums[cur]);以上这两个代码组合起来后，这个题的代码便就结束了，这个题目是小编系统学习算法题的第一个题目，隔了这么久，我认为这个题目还是比较容易的相对于后面我要讲的，下面小编就展示这个题目的代码以及通关图片。
class Solution {
public:
void moveZeroes(vector<int>& nums)
{
for(int cur = 0,dest = -1;cur < nums.size() ; cur++ )
{
if(nums[cur]) //这就代表这非0元素
std::swap(nums[++dest],nums[cur]);
}
}
}; 
2.复写零
1.1.题目展示
在讲述这个题目的解决方法之前，小编先展示这个题目：1089. 复写零 - 力扣（LeetCode）
1.2.题目解答
老规矩，我们先来看一下这个题目的内容是什么，阅读此题，我们不难发现，这个题目的操作其实就和标题一样，我们遍历数组，倘若遇到了0，那么就把0写两遍，并且把其他元素往右平移，值得注意的是，这个题目的复写0操作并不会让数组扩容，我们复写到原数组最后一个位置即可，剩下的元素可以抛弃，并且我们是在原数组的基础上进行复写操作的，并不让我们多开辟数组，这个点要注意，所以小编个人认为这个题目的难度应该不局限于简单，感觉算是一个偏中等的题目，倘若这个题目允许我们自己开辟一个数组的话，那么难度肯定就是简单，下面我们废话不多说，开始进入题目思路的讲解。
1.3.题目思路讲解
本题乍一看很容易，但实际操作起来各位可能就知道这个题目的难度在哪里了，因为我们看到这个题目的第一印象就是去自己在开辟一个新的数组，然后把内容都复制到那个数组里面，这么做的话到是很容易，但很可惜这个题目不让我们这样去做，但是我们可以借助这个思想去解决问题，我们可以先进行“异步”操作，然后在进行“同步”操作，简单来说，我们先去自己通过开辟数组的方法先做一遍这个题目，然后在原数组的基础上进行修改，下面小编新进行异步操作的讲解：
首先，我们先准备一个要复写零的数组，这里我直接用力扣给出的例子来解释了：
此时我们需要准备两个“指针”，一个是负责遍历原数组的元素，一个是控制新数组，把原数组的内容复制到新数组的，此时cur指向0，dest指向-1，如下图所示：
通过上图可以知晓我说的内容，此时我们让cur遍历，如果遇到非0，让dest往后走一步，然后就把元素给予dest，然后cur往后走一步；倘若此时cur为0，先让dest往后走一步，就让此时的dest为0，然后让dest往后再走一步，然后dest在为0【此时还需要判断一下dest是否已经到了末尾，如果是末尾的话直接结束循环，在访问就越界了】，这些工作做完以后让cur往后走一步，然后循环下去，直到dest走到数字最后一个位置便结束了，此时便就完成了复写零操作，结果就如下图所示：
此时我们就完成了复写零的操作，只不过这是“异步”操作，而不是我们想要实现的“同步”操作，但是我们可以参考异步进行同步处理，此时我们不难发现，此时cur的位置就是最后一个要复写的位置，我们可以依据这个进行同步操作，可能这个时候就有读者朋友要说了，我直接在开头用双指针进行操作不就好了？其实这样是不对的，这样做是会出现覆盖元素的情况，此时我们就很难去完成复写零的操作，对此疑惑的读者朋友可以自己去实操一下，有时候光我说是不可以的，实践出真知，自己实操一遍总比看别人说要强；
这个题的解决方法是从最后一个位置开始进行双指针操作，也就是从后往前进行复写操作，此时我们就要巧用cur这个位置，此时的dest是会在数组最后一个位置的（可能会出现越界操作，这我会在之后的代码部分详细告诉各位如果解决的），我们先检测cur位置的数据，如果是非0，那么让cur的数据覆盖dest的数据，之后我们就让cur和dest都往前走一步；如果是0，那么此时就先让dest位置的数据为0，然后让dest再往前走，让此时dest位置的数据还是为0，然后让cur往前走；这样通过循环的方式我们就可以实现复写零的操作，下面小编进行代码方面的讲解。
1.4.代码实现
想要找到最后一个位置出现的数据，我们就要先借助一下一个循环来进行实现，此时我们准备好两个“指针”，一个是cur为0，在数组的开头，一个是dest，为-1（为了保证它在的位置是数组最后一个位置）；然后我们就开始循环：如果此时的cur为0的话，dest往后走两步，否则就走一步；然后我们判断此时的dest是否到了数组最后一个位置，如果到了就结束循环；如果此时的dest超出了数组一个单位，就代表着，此时的cur为0，并且dest恰好在数组最后一个位置的前一个位置，这样就会出现越界的问题，这个情况一定要考虑到，考虑题目要全面，不然我们就很容易走进一个坑里，此时我们让数组最后一个的数据为0，并且让cur往前走一步，dest往前走两步，然后结束循环；如果此时这两个条件都没有达成，按摩就让cur继续往后走一步来进行遍历，代码如下图所示：
int cur = 0, dest = -1;
while (dest < (int)(arr.size() - 1)) //这里一定要小心整形提升的问题，因为arr.size是无符号整形，所以它会默认把左边弄成无符号整形，-1的无符号整形其实就是
{
if (arr[cur] == 0)
{
dest += 2;
}
else
dest++;
if (dest == arr.size() - 1)
break;
if (dest == arr.size())
{
arr[arr.size() - 1] = 0;
cur--;
dest -= 2;
break;
}
cur++;
}对了，此时有个大坑我一定要说，学过vector容器的朋友都知道，vector的size接口返回的是一个无符号整型，如果我们此时不管不顾的话，那么此时的dest也会整型提升，升级为无符号整型，要知道，-1的无符号整形是很大的，所以这样直接会让这个题目过不去，此时我们就要进行强制类型转换操作，让无符号的变成有符号的，这样就不会出错了，我踩过的坑就不让各位踩了┭┮﹏┭┮。
之后我们就要用双指针进行往前复写零操作了，此时其实蛮简单的，如果此时的cur所在位置的值不为0，那么让cur位置的值把dest位置的值给覆盖了，然后让cur和dest统一往前走一步；如果此时的cur位置的值就是0，那么就更好说了，我们让此时dest位置的值为0，然后dest继续往前走，还为0；然后我们再让dest和cur统一往前走一步就好了，此时我是巧用了循环，通过循环让dest位置的值为0，最后让cur往前走一步就好了，代码如下所示：
while ((int)cur >= 0 && (int)dest >= 0)
{
if (arr[cur])
{
arr[dest] = arr[cur];
cur--;
dest--;
}
else if (arr[cur] == 0)
{
for (int i = 0; i < 2; i++)
{
arr[dest] = 0;
dest--;
}
cur--;
}
}此时这个题目的代码我们就写完了，虽然从这个位置说有点晚了，但小编推荐看我后来博客的读者朋友，可以先看完题目思路讲解，自己敲一遍代码，然后看看自己的过了没，如果过了的话，那么就没必要看我的代码展示了，当然如果时间丰富并且想要学习一下我的代码书写的话，那么欢各位去纠正我的错误，不过千万不要直接来看我的代码展示，这么做是永远提高不了自己的算法能力的，下面我给出完整的代码展示：
class Solution {
public:
void duplicateZeros(vector<int>& arr) {
int cur = 0, dest = -1;
while (dest < (int)(arr.size() - 1)) //这里一定要小心整形提升的问题，因为arr.size是无符号整形，所以它会默认把左边弄成无符号整形，-1的无符号整形其实就是
{
if (arr[cur] == 0)
{
dest += 2;
}
else
dest++;
if (dest == arr.size() - 1)
break;
if (dest == arr.size())
{
arr[arr.size() - 1] = 0;
cur--;
dest -= 2;
break;
}
cur++;
}
while ((int)cur >= 0 && (int)dest >= 0)
{
if (arr[cur])
{
arr[dest] = arr[cur];
cur--;
dest--;
}
else if (arr[cur] == 0)
{
for (int i = 0; i < 2; i++)
{
arr[dest] = 0;
dest--;
}
cur--;
}
}
}
};3.总结
这是小编第一次专门写算法的文章，以前我写过的算法文章都是类似课后题的形式，也不算算法题的完整讲解，所以我讲解难免会出现一些问题，就比如子写错了，代码不对，思路不对等等问题，如果有问题的话，欢迎各位在评论区“批判”我，我很乐意接受各位的批评，相信在各位的批评下我会在之后的算法文章的撰写会越来越严谨，希望大家可以一起共勉，那么各位大佬们，说再见的时候到了，我们下一篇文章见啦~
