引言
常见的双指针有两种形式，一种是对撞指针，一种是快慢指针。
对撞指针：一般用于顺序结构中，也称左右指针。从两端向中间移动。终止条件一般是两个指针相遇或者错开（left == right 或 left > right）。 快慢指针：又称为龟兔赛跑算法，基本思想是使用两个移动速度不同的指针在数组或链表等序列结构上移动。常用于处理循环往复的情况。 ***注意：***这里的指针并不是 C 语言中的地址指针，而是用变量记录数组下标。
283. 移动零
题目描述
实现核心及思路
解题思路： 对撞指针方案行不通，因为题目要求移动 0 元素的同时还要保证非零元素的相对顺序。采用两个指针都从数组的左端出发，把非零的元素依次找到放在前面，最后剩下 0 自然就排在数组后面了。
- 刚开始让一个指针 cur 先指向数组的第一个元素，另一个指针 dest 初始化为 -1。cur 用来找非零元素，dest 用来确定 cur 之前的 0 元素。
- 当 cur 指向的元素为零则 cur++，继续向后找非零元素来将前面的 0 交换到后面；
- 当 cur 指向的元素不为 0，则让 dest 向前移动一位（dest++），然后交换 cur 和 dest 指向的元素，cur 继续向后移动（cur++）。
- 结束条件：当 cur 走到数组尾部的时候意味着所有非零元素都找到了，结束。
思路可视化：
代码实现：
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int size = nums.size();
int dest = -1;
int cur = 0;
while(cur < size) {
if(nums[cur] != 0) {
dest++;
swap(nums[dest], nums[cur]);
}
cur++;
}
}
};
代码测试：
int main() {
Solution s;
vector<int> v1{ 1,0,2,0,3,0,4 };
vector<int> v2{ 0,0,0,6,5,4 };
s.moveZeroes(v1);
for (auto e : v1) { cout << e << " "; }
cout << endl;
s.moveZeroes(v2);
for (auto e : v2) { cout << e << " "; }
return 0;
}
1089. 复写零
题目描述
实现核心及思路
解题思路： **解法一：**额外创建一个等大的数组，遍历原数组，遇到 0 写入两次。但题目限制在原数组操作。 **解法二：**观察示例可知，最终输出结果会覆盖原有数据。考虑从后往前遍历数组来复写零。问题转化为：先找最后一个有效元素，然后从该位置开始从后往前遍历复写零。 **步骤一：**利用双指针法找最后一个有效元素位置。cur 指针开始指向第一个元素，定义 dest 指针（初始化为 -1）。当 cur 指向非零元素，dest 向后移动一位；当 cur 指向零元素，dest 向后移动两位。结束条件：dest < size - 1。
***细节一：***当进入循环后发现 dest 移动两次后到了数组的末尾，此时不能再让 cur 向前移动了，否则数组空间不够。 **步骤二：**继续利用双指针法，cur 指向最后一个有效数据，dest 指向数组的最后。从 cur 开始向前遍历。非零元素写一次，0 元素写两次。结束条件：cur >= 0。 ***细节二：***当 cur 指向最后一个有效数据且为 0 时，dest 需要向后移动两次，但数组空间只剩一个位置。意味着这个 0 只能复写一次，需单独处理。
思路可视化：
代码实现：
class Solution {
public:
void duplicateZeros(vector<int>& arr) {
int cur = 0;
int dest = -1;
int size = arr.size();
while (dest < size - 1) {
if (arr[cur] == 0) dest += 2;
else dest++;
if (dest < size - 1) cur++;
}
if (dest >= size) {
arr[size - 1] = 0;
dest = size - 2;
cur--;
}
while (cur >= 0) {
if (arr[cur] == 0) {
arr[dest--] = 0;
arr[dest--] = 0;
} else arr[dest--] = arr[cur];
cur--;
}
}
};
代码测试：
int main() {
Solution s;
vector<int> v1{ 1, 0, 2, 3, 0, 4, 5, 0 };
vector<int> v2{ 1, 0, 2, 3, 0, 4, 5 };
vector<int> v3{ 1, 0, 2, 3, 0, 4 };
s.duplicateZeros(v1);
s.duplicateZeros(v2);
s.duplicateZeros(v3);
for (auto e : v1) cout << e << " "; cout << endl;
for (auto e : v2) cout << e << " "; cout << endl;
for (auto e : v3) cout << e << " ";
return 0;
}
202. 快乐数
题目描述
实现核心及思路
解题思路： 对于 n = 19，经过求和后结果为 1，即为快乐数；n = 2，经过求和又回到了起点。 结论：对于每个非零整数，进行上面的操作，要么最终得到 1，要么进入一个循环。对于这种循环的问题，均可以用快慢指针的方法解决。 假设慢指针一次走一步，快指针一次走两步，那么快指针一定先入环，但由于两者的速度差，最终肯定会相遇。 对于这个题而言：慢指针走一步即对应一次求和，快指针走两步即对应连续求和两次。 结束条件：当快慢指针相遇。如果相遇时，快慢指针指向的和为 1，这个数即为快乐数；反之，则不是。
代码实现：
class Solution {
public:
int Sum(int n) {
int sum = 0;
while(n) {
int a = n%10;
sum += pow(a,2);
n/=10;
}
return sum;
}
bool isHappy(int n) {
int slow = Sum(n);
int fast = Sum(n);
fast = Sum(fast);
while(slow != fast) {
slow = Sum(slow);
fast = Sum(fast);
fast = Sum(fast);
}
if(slow == 1) return true;
else return false;
}
};
11. 盛水最多容器
题目描述
实现核心及思路
解题思路： **解法一：**暴力解法，两次 for 循环，算出所有的体积，找出最大值。 解法二：对撞指针（左右指针），left 和 right 指针向右向左找符合的桶。依靠单调性，当 left 和 right 向内移动时，宽度一定是变短的，体积 V = 宽度 * 高，所以要想找到最大的体积，只能依靠找到更大的高度。 让 left 和 right 中指向高度较小的一个向内移动，找更大的高度，才有可能使体积更大。同时，每次计算一个体积，通过比较获得最大体积。
💡库当中有一个 max 函数可以帮我们找两个数中的较大值，头文件
思路可视化：
代码实现：
class Solution {
public:
int maxArea(vector<int>& height) {
int left = 0;
int right = height.size() - 1;
int m = 0;
while(left < right) {
int h = height[left] > height[right] ? height[right] : height[left];
int V = (right - left) * h;
m = max(m,V);
if(height[left] < height[right]) left++;
else right--;
}
return m;
}
};
