双指针 — 复写零
目录
1. 题目解析
2. 算法讲解
1.算法原理
2.“异地”操作
3.“就地”操作
误解
正解
从后往前完成复写操作
找到最后一个复写的数
处理边界情况
3. 编写代码
正解顺序
1.找到最后一个复写的数
2.处理边界情况
3.从后往前完成复写操作
性能分析：
完整代码（大神版）：
1. 题目解析
1089.复写零
题目中的限制条件：
请不要在超过该数组长度的位置写入元素。请对输入的数组 就地 进行上述修改，不要从函数返回任何东西。
如果这个题没有以上的限制条件，暴力解题会非常简单，但是因为这个限制条件，难度就直线上升了，并且容易被LeetCode给的难度迷惑；
以下图的数组为例：
根据题意，如果遍历到遇到0，就写两遍，其他数字写一遍，直到写满数组的固定长度为止。
2. 算法讲解
1.算法原理
解法：双指针算法
双指针算法并不是凭空来的，而是先根据“异地”操作，然后优化成双指针下的“就地”操作 。
“异地”操作：新创建一个数组，根据原数组和修改条件，对新数组进行相应的修改；
“就地”操作：在原有数组的基础上，根据修改条件，对原数组进行修改。
2.“异地”操作
如果我们先不管题目的限制条件，通过“异地”操作，完成对数组复写零，那么该怎么写呢 ？
我们定义两个指针，cur遍历原数组，dest遍历新数组；
cur从原数组0下标开始，dest从新数组0下标开始：
在遍历的过程中，
cur遇到非0元素，则dest在新数组上写一遍：
cur遇到 0元素，则dest在新数组复写两遍：
dest写好后，cur向后移动一位，dest再向后移动一位，直到dest走出数组为止：
3.“就地”操作
我们写完异地操作后，接下来，我们要在刚刚的基础上，模拟优化异地操作的就地操作。
误解
刚开始，dest和cur两个指针，都指向数组0下标。
当cur指向1时，cur和dest直接往后移动一位；cur指向0时，如果直接抄两遍，把1下标和2下标全改成0，这时候原来3下标的元素2就丢失了：
这是错的。所以，在原数组上，从左到右修改数组，是解决不了问题的，因为会覆盖后面的数据。
删除数组中值为val的题目，就是先通过异地操作模拟得到规律，再优化成就地操作双指针，发现就能直接解决该问题；（从要删除的val所在的元素下标开始，从后往前覆盖元素）
因为删除数组中值为val的元素这个题，dest肯定是在cur之后的，覆盖元素时，不会让除val以外的元素丢失，因此可以直接使用就地操作双指针完成；
但是，复写会覆盖原来的数据，因此不能直接从左向右修改数组，那我们试试从右往左修改数组。
正解
从后往前完成复写操作
从又向左修改数组，dest指向最后一个元素，cur指向最后一个复写的元素。以下图的数组为例：
（上图表示数组前后变化情况）
假设我们已经提前知道：通过复写零的规则，最后一个被复写的元素是4；
所以刚开始cur指向数组6下标的4元素，dest指向数组最后一个元素0：
接下来，我们要通过cur指向的元素的值，来让dest对数组作出相应的修改 ：
当cur指向4，就修改dest指向的元素为4：
处理好后，让cur和dest同时向前移动一位：
cur遍历到的数组元素为0时，这时候，令dest指向的元素为0，并且cur先不动；dest再往前一步，再令dest指向的元素为0：
完成以上步骤后，再调整cur和dest同时向前移动一位：
通过上面cur遍历到的元素，让dest作出对数组不同的修改方法，注意在dest修改好后，cur和dest都要往前移动一位，最后结果：
整个过程，dest的调整都是基于cur遍历到的元素的值；刚开始cur的位置，为最后一个要写的元素的位置；
只要cur的位置找对了，我们就会发现：cur始终在dest之前；所以整个循环条件为cur>=0。
所以，以上就是第二步操作，从后往前完成复写操作，接下来，需要重点讲第一步操作，先找到最后一个复写的数
找到最后一个复写的数
要找到最后一个复写的数，可以用双指针算法 ：
定义一个指针cur指向数组第一个元素，dest指向-1；
因为，刚开始，我们并不知道复写的最后一个数在哪，所以dest指向-1的位置，cur的作用是从前往后遍历数组，决定dest向后移动一步，还是两步。
循环结束条件dest<array.length（dest指向数组最后一个元素的位置即可结束循环）
双指针算法：
1.先判断 cur 位置的值；
2.决定 dest 向后移动一步（cur指向的元素非0）或者两步（cur指向的元素为0）；
3.判断一下 dest 是否已经到数组最后一个元素的位置；
4.dest 还没有到数组最后一个元素的位置，cur++
此时，dest在数组最后一个元素的位置，cur指向的元素，就是最后一个被复写的数。
处理边界情况
按照上面的两步，提交还是无法通过，因为会有一个特例：
要找到上面数组中，最后一个复写的数：
我们可以看到，对于上面的一个特例，通过双指针算法，如下图：最后dest是无法停在数组最后一个元素的位置上的，dest会发生越界；在leetcode上，只要有用例发生越界，那么整个代码就无法通过。
所以，cur没有问题的时候，dest是有可能出现问题的；因此，我们在从后往前复写的操作前，还要加一步操作，处理一下边界情况。
怎么处理边界情况呢？
出现越界的情况，一定是cur等于0，导致dest直接越界；
按照从后往前复写的操作，会把最后一个元素和dest指向的数组越界位置，都修改成0，这时候就越界访问了：
此时，不能把两个位置(length-1和length)都修改成0；
只需要把数组最后一个元素（length-1）修改成0即可。
把length-1位置的值修改成0，然后，我们让dest从后往前走两步，cur从后往前移动一步，然后正常复写即可。(这是一种特殊的越界情况，直接单拎出来特殊处理)
接下来，我们再进行复写操作，就不会出现越界情况
3. 编写代码
正解顺序
我们同时可以看看小白和大神写的代码差别在哪里？
1.找到最后一个复写的数
2.处理边界情况
3.从后往前完成复写操作
按照小白的写法，哪怕知道这道题的解法，但是在leetcode上会因为代码的繁琐而超时（狗头）：
性能分析：
简单分析一下时空复杂度：
对于时间复杂度，虽然这里有两个while循环，但是常数级别是可以忽略的，所以时间复杂度还是O(N)的，所以相当于，一次遍历数组，我们就完成了复写操作。
空间复杂度，这里只用了有限的三个变量，所以是O(1)
完整代码（大神版）：
class Solution {
public void duplicateZeros(int[] arr) {
int dest=-1,cur=0,n=arr.length;
//1.找到最后一个复写的数
while(dest<n){
if(arr[cur]!=0){
dest++;
}else {
dest+=2;
}
if(dest>=n-1)break;
cur++;
}
//2.处理边界情况
if(dest==n){
arr[n-1]=0;
cur--;
dest-=2;
}
//3.从后往前完成复写操作
while(cur>=0){
if(arr[cur]!=0){
arr[dest--]=arr[cur--];
}else {
arr[dest--]=0;
arr[dest--]=0;
cur--;
}
}
}
}