双指针算法实例1（移动零）

常⻅的双指针有两种形式：

1 对撞指针（左右指针）：

a 对撞指针从两端向中间移动。⼀个指针从最左端开始，另⼀个从最右端开始，然后逐渐往中间逼
近

b 终止条件一般是两指针相遇or错过（也可能在循环过程中找到结果直接跳出循环），即

    left == right （两个指针指向同⼀个位置）
    left > right   （两个指针错开）

2 快慢指针：

   使⽤两个移动速度不同的指针在数组或链表等结构上移动

   特别是处理环形链表或数组时有很大用处，也就是说当问题出现循环往复的情况时，可考虑使用快慢指针的思想

题目：

给定一个数组 ，编写一个函数将所有 移动到数组的末尾，同时保持非零元素的相对顺序。nums0

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

 

示例 1:

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

示例 2:

输入: nums = [0]
输出: [0]

代码实现：

class Solution
{
public:void moveZeroes(vector<int>& nums){int cur = 0;//遍历数组int pre = -1;//指向非0元素区域中最后一个非0元素while(cur<nums.size()){if(nums[cur])//找到非0元素{swap(nums[++pre],nums[cur]);//将非0元素与0元素交换，++pre指向的一定是0元素}cur++;}}
};

思路详解：

题目要求实现的功能，可以说是数组划分（数组分块）让非0元素排在前半部分，0元素排在后半部分，且要求元素间的相对顺序保持不变。

方法：

前后指针法

（此处的指针是用数组的下标来充当的，并不是真正意义上的指针）

1 cur指针去从左向右遍历数组（只需要一直向前走就行）指向的是待处理的元素

2 pre指针记录已处理区间内的非0元素区域，最后一个非0元素的下标

cur初始化为0，因为要从0下标开始遍历

pre初始化为-1，因为pre指向的是已处理区间中的非0元素区的最后一个非0元素下标，刚开始还没有确定任何一个元素是否是非0元素

思想：

cur负责遍历数组，指向待处理的元素：

找到的是非0元素，则将它交换到前面

找到的是0元素，则视而不见，直接++走向下一个待处理元素

pre指向的始终是已处理区间中的非0元素区的最后一个非0元素的下标，cur因为遇到0而不断++，与pre拉开距离

那么[pre+1,cur-1]的区间是已处理区间中的0元素区

在处理过程中，数据分三区：

[0,pre]：全都是非0元素

[pre+1,cur-1]：全是0元素

[cur,n-1]：n是数组元素个数，是待处理的元素

 

简单来说，就是cur在遍历过程中若是遇到非0元素，则将它与0元素交换，让非0元素换到前面，0元素换到后面，[pre+1,cur-1]的区域内全是0元素，遇到0元素则不管，直接++找下一个待处理元素

完结撒花~ 

题外话：解决此题目的前后指针法其实和快排中实现数组划分的方法之一类似，也可以成之为前后指针法，但是实现略有差异，且在实现后，快排中数组元素的相对顺序可能会发生改变

详情在我的另一篇快排模拟实现的博客中：

http://t.csdn.cn/2Km96