目录
双指针算法介绍
练习：移动零
双指针算法介绍
双指针算法常见于数组和双向链表的题型
在数组中，双指针中的指针代表数组元素的下标，而不是真正的指针类型变量
在双向链表中，双指针中的指针即为真正意义上的指针，该指针一般是双向链表节点类型的指针
常见的双指针有两种形式：
- 对撞指针：从结构的两端开始向中间移动，一般存在两种情况
left == right：代表两个指针指向的时同一个位置left > right：代表连个指针已经相遇过一次，相遇的下一次形成交错
- 快慢指针：所谓快慢指针即为一个指针走得快，一个指针走得慢
- 快慢指针一般的思路是：慢指针走一步，快指针走两步
练习：移动零
题目链接：283. 移动零 - 力扣（LeetCode）
给定一个数组nums，编写一个函数将所有0移动到数组的末尾，同时保持非零元素的相对顺序。
请注意 ，必须在不复制数组的情况下原地对数组进行操作。
思路解析：
本题可以采用双指针算法进行解决，定义一个指针cur和dest，通过这两个指针构建出三个区间，分别是：
- [0, dest] 代表已处理区间中的非0部分
- [dest+1, cur-1] 代表已处理的区间中的0
- [cur, nums.size()-1] 代表未处理的区间
当每一次的遍历移动数据后形成的区间满足上面三个区间的内容，则代表最后结果正确，如图所示：
此时的区间[0, dest]为不存在的区间，所以不存在非0部分，而[dest+1, cur-1]也为不存在区间，[cur, nums.size()-1]区间中有一个未处理数据0
操作的基本思路为：
- 当遇到0时：dest不动，cur向前走一步
- 当遇到非0时：dest向前走一步，交换dest的数据和cur的数据
- 交换完毕后：cur向前走一步
在上面的区间中[0, dest]区间中有一个数字1，[dest+1, cur - 1]区间中存在一个数字0，[cur, nums.size()-1]区间中均为未处理的数据
在上面的区间中[0, dest]区间中有数字1和3，[dest+1, cur - 1]区间中存在两个数字0，[cur, nums.size()-1]区间中均为未处理的数据
在上面的区间中[0, dest]区间中有数字1、3和12，[dest+1, cur - 1]区间中存在连个数字0，[cur, nums.size()-1]区间不存在，此时数组已经遍历交换完成，所有的数字零移到了数组的末尾，并且没有改变数组非0元素的相对位置
参考代码：
/*
* @lc app=leetcode.cn id=283 lang=cpp
*
* [283] 移动零
*/
// @lc code=start
class Solution
{
public:
void moveZeroes(vector<int> &nums)
{
// 记录已处理的区间中最后一个非零元素的位置
int dest = -1;
// 遍历数组
int cur = 0;
while (cur < nums.size())
{
// 遇到0不交换
if (nums[cur] == 0)
{
cur++;
}
else
{
// 遇到非0元素交换dest下一个位置的数据和cur位置的数据
swap(nums[++dest], nums[cur++]);
}
}
}
};
// @lc code=end或者写成下面的形式：
/*
* @lc app=leetcode.cn id=283 lang=cpp
*
* [283] 移动零
*/
// @lc code=start
class Solution
{
public:
void moveZeroes(vector<int> &nums)
{
for (int cur = 0, dest = -1; cur < nums.size(); cur++)
{
if (nums[cur])
{
swap(nums[++dest], nums[cur]);
}
}
}
};
// @lc code=end
