双指针算法简介
双指针算法是解决算法题中常见的一种方法，主要分为对撞指针和快慢指针两种。
对撞指针
一般用于顺序结构，也叫左右指针。
实现思路：
- 对撞指针从序列两端向中间移动。
- 终止条件一般是两个指针相遇或错开。
快慢指针
又称龟兔赛跑算法，使用两个移动速度不同的指针在序列上移动。常用于环形链表或数组中。
实现思路：
- 研究问题是否有循环往复的现象。
- 设置一个快指针和一个慢指针，例如让快指针移动两步，慢指针移动一步。
相关例题
题目一：移动零
题目描述
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。必须在不复制数组的情况下原地对数组进行操作。
示例 1:
输入：nums = [0,1,0,3,12]
输出：[1,3,12,0,0]
示例 2:
输入：nums = [0]
输出：[0]
提示:
1 <= nums.length <= 10^4-2^31 <= nums[i] <= 2^31 - 1
实现思路
思路一
统计非零数的个数，将非零数依次交换到数组开头。
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int cnt = 0;
for (auto& s : nums) {
if (s == 0) cnt++;
}
cnt = nums.size() - cnt;
int k = 0;
for (int i = 0; i < nums.size(); i++) {
if (nums[i] != 0) {
swap(nums[i], nums[k++]);
}
if (k > cnt) break;
}
}
};
思路二
设置一个头指针，将非零数直接向头位置替换，无需计算个数。
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int cnt = 0;
for (int i = 0; i < nums.size(); i++) {
if (nums[i]) {
swap(nums[i], nums[cnt++]);
}
}
}
};
优化方案
体现双指针标准流程。定义 cur 扫描数组，dest 记录非零序列最后一个位置。遍历过程中 [0, dest] 为非零元素，[dest - 1, cur - 1] 为零元素。
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int n = nums.size();
for (int i = 0, cur = 0, index = -1; i < n; i++) {
if (nums[i]) {
swap(nums[++index], nums[i]);
}
}
}
};
题目二：复写零
题目描述
给你一个长度固定的整数数组 arr，将该数组中出现的每个零都复写一遍，并将其余的元素向右平移。注意不要超过该数组长度的位置写入元素。请就地修改。
示例 1：
输入：arr = [1,0,2,3,0,4,5,0]
输出：[1,0,0,2,3,0,0,4]
示例 2：
输入：arr = [1,2,3]
输出：[1,2,3]
实现思路
思路一
判断特殊情况。找到复写后数组最后一个元素复写前的下标。使用双指针，一个指针 i 遍历找下标，一个指针 cnt 计数。若 cnt 等于 n 说明所有零都复写了，否则有超出范围的情况。从后往前遍历进行复写。
class Solution {
public:
void duplicateZeros(vector<int>& arr) {
int n = arr.size();
int cnt = 0;
int i = 0;
for (; i < n && cnt < n; i++, cnt++) {
if (arr[i] == 0) cnt++;
}
bool flag = false;
if (cnt == n) flag = true;
int k = i - 1;
for (int j = k; j >= 0 && n >= 0; j--) {
if (arr[j] || (j == k && !flag)) {
if (n > 0) arr[--n] = arr[j];
} else {
if (n > 0) arr[--n] = 0;
if (n > 0) arr[--n] = 0;
}
}
}
};
思路二
初始化 cur = 0, dest = 0。找到最后一个复写的数。若 dest 越界则单独处理。从 cur 往后开始遍历数组，复写出结果数组。
class Solution {
public:
void duplicateZeros(vector<int>& arr) {
int cur = 0, dest = -1, s = arr.size();
while (cur < s) {
if (arr[cur]) dest++;
else dest += 2;
if (dest >= s - 1) break;
cur++;
}
if (dest == s) {
arr[s - 1] = 0;
dest -= 2;
cur--;
}
while (cur >= 0) {
if (arr[cur]) arr[dest--] = arr[cur--];
else {
arr[dest--] = 0;
arr[dest--] = 0;
cur--;
}
}
}
};
