C++算法
C++ 双指针算法详解：对撞与快慢指针实战
本文介绍了 C++ 中双指针算法的核心应用，涵盖对撞指针与快慢指针两种模式。通过移动零、复写零、盛最多水的容器及快乐数四个经典例题，详细解析了算法思路、代码实现及复杂度分析。重点阐述了如何利用双指针优化数组遍历效率，将时间复杂度从 O(n^2) 降至 O(n)，并提供了完整的 C++ 代码示例供参考学习。
本文介绍了 C++ 中双指针算法的核心应用，涵盖对撞指针与快慢指针两种模式。通过移动零、复写零、盛最多水的容器及快乐数四个经典例题，详细解析了算法思路、代码实现及复杂度分析。重点阐述了如何利用双指针优化数组遍历效率，将时间复杂度从 O(n^2) 降至 O(n)，并提供了完整的 C++ 代码示例供参考学习。
题目链接：283. 移动零
题目描述：给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
此题的主要思路是通过双指针法，使所有非零元素依次移动到数组前部，零元素则自动归到数组的后部。具体思路如下：
cur：遍历整个数组。dest：指向最后一个非零元素的位置，初始化为 -1（因为不知道数组第一个元素是不是 0）。cur 指向非零元素，并且 ++dest != cur，则将其放置在 dest + 1 的位置。cur 遇到 0 时，不做任何操作，只移动 cur。cur 遍历完整个数组后，dest + 1 后的所有位置自动归零，完成所需操作。假设数组初始为 [0, 1, 0, 3, 12]：
cur = 0，dest = -1。nums[cur] 是 0，cur 右移，dest 保持不动。cur = 1，nums[cur] = 1。dest = -1，非零元素 1 应插入到 dest + 1 = 0 位置上。nums[++dest] 和 nums[cur]，即 nums[0] 和 nums[1]，数组变为 [1, 0, 0, 3, 12]。cur = 3，nums[cur] = 3。dest = 1。3 插入 dest + 1 = 2 位置上，交换后数组变为 [1, 3, 0, 0, 12]。cur = 4，nums[cur] = 12。dest = 2。12 插入 dest + 1 = 3 位置上，交换后数组变为 [1, 3, 12, 0, 0]。步骤图解：
| Iteration | cur Pointer | dest Pointer | Array State |
|---|---|---|---|
| 1 | 0 | -1 | [0, 1, 0, 3, 12] |
| 2 | 1 | 0 | [1, 0, 0, 3, 12] |
| 3 | 3 | 1 | [1, 3, 0, 0, 12] |
| 4 | 4 | 2 | [1, 3, 12, 0, 0] |
class Solution {
public:
void moveZeroes(vector<int>& nums) {
for (int cur = 0, dest = -1; cur < nums.size(); cur++) {
if (nums[cur] != 0 && ++dest != cur) {
swap(nums[dest], nums[cur]);
}
}
}
};
dest 从 -1 开始，以便于将第一个非零元素移动到 0 位置。++dest 和 cur 指向的元素交换，否则会造成非零元素错位。nums[cur] 为非零时才交换，避免多余的操作。在代码执行中，非零元素会依次覆盖零元素的位置，最终达到将所有零移动到数组末尾的目的。此方法的时间复杂度为 O(n)，空间复杂度为 O(1)，即为原地操作，不占用额外空间。
这个方法是往后我们学习「快排算法」的时候，「数据划分」过程的重要一步。如果将快排算法拆解的话，这一段小代码就是实现快排算法的核心步骤。
题目链接：1089. 复写零
题目描述：给定一个固定长度的整数数组 arr，在遇到每个零时，将其右移并插入一个零，同时保持数组长度不变。
因为数组的零元素会被重复写入两次，如果直接从前向后遍历会导致覆盖，因而最优解是使用双指针从后往前复写。算法分为两步：
cur：用来找到被复写后数组的最后一个数在原来数组的位置，初始化为 0。dest：用于模拟复写过程，初始为 -1。cur 遍历数组：
arr[cur] 非零，则 dest++。arr[cur] 为零，则 dest += 2。dest 大于或等于 n - 1（数组最后一个位置），则退出循环。dest == n，表示需要在最后填入一个零。arr[n - 1] 设置为零，并调整 cur-- 和 dest -= 2 以适应边界复写。cur 开始复写至 dest，若 arr[cur] 为零则复写两次，否则只复写一次。class Solution {
public:
void duplicateZeros(vector<int>& arr) {
int cur = 0, dest = -1, n = arr.size();
// 1. 寻找最后一个需要复写的数
while (cur < n) {
if (arr[cur]) dest++; // 非零元素，dest 右移一位
else dest += 2; // 遇零时，dest 右移两位
if (dest >= n - 1) break; // 越界则退出循环
cur++;
}
// 2. 处理边界情况，dest == n 时需在末尾填零
if (dest == n) { arr[n - 1] = 0; cur--; dest -= 2; }
// 3. 从后向前复写元素
while (cur >= 0) {
if (arr[cur]) { arr[dest--] = arr[cur]; } // 非零元素，复写到 dest 位置
else {
arr[dest--] = 0; // 遇到零时，连续写两次
arr[dest--] = 0;
}
cur--;
}
}
};
假设数组为
arr = [1, 0, 2, 3, 0, 4, 5, 0]：
步骤 1：找到最后一个需要复写的元素
cur = 0，dest = -1，n = 8dest 向后移动两位，遇到非零元素时 dest 向后移动一位。目标是找到最后一个需要复写的元素位置 cur。遍历示例：
cur = 0，arr[0] = 1，dest++，所以 dest = 0cur = 1，arr[1] = 0，dest += 2，所以 dest = 2cur = 5，dest = 7，在此位置结束循环。步骤 2：逆序填充
在此时，cur 为 5，dest 为 7。从这两个位置开始逆序复写，以避免前面的零覆盖其他元素：
| Iteration | cur | dest | Array State |
|---|---|---|---|
| Start | 5 | 7 | [1, 0, 2, 3, 0, 4, 5, 0] |
| 1 | 4 | 6 | [1, 0, 2, 3, 0, 4, 5, 4] |
| 2 | 3 | 3 | [1, 0, 2, 3, 0, 0, 0, 4] |
| 4 | 1 | 2 | [1, 0, 2, 2, 3, 0, 0, 0] |
| 5 | 1 | 2 | [1, 0, 0, 2, 3, 0, 0, 0] |
| Final | 0 | 1 | [1, 0, 0, 2, 3, 0, 0, 4] |
具体操作解释：
cur = 5，dest = 7，将 arr[5] 的值 4 复制到 arr[7]。cur = 4，在 arr[6] 和 arr[5] 连续填入 0。cur = 3，将 arr[3] 的值 3 复制到 arr[4]。cur = 2 和 cur = 1 分别填入 2 和两个 0。[1, 0, 0, 2, 3, 0, 0, 4]。dest 从 -1 开始，以保证 cur 准确定位复写后数组最后一个元素在原来数组的位置。dest 超出数组边界时，最后一个位置设为零，并调整 cur 和 dest。O(n)，只需遍历两次。O(1)，仅使用少量额外变量。给定一个长度为 n 的整数数组 height，有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i])。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明：你不能倾斜容器。
示例 1：
[1,8,6,2,5,4,8,3,7]49[1,8,6,2,5,4,8,3,7]。在这个情况下，能够容纳水（表示为蓝色部分）的最大值是 49。算法思路：
i 和 j 分别指向容器的最左端和最右端，此时容器的宽度为 j - i。由于容器的高度由两条边中较短的决定，因此容积的公式为：
v = (j - i) * min(height[i], height[j])
代码实现：
class Solution {
public:
int maxArea(vector<int>& height) {
int n = height.size();
int ret = 0;
// 两层 for 循环枚举出所有可能出现的情况
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
// 计算容积，找出最大的那一个
ret = max(ret, min(height[i], height[j]) * (j - i));
}
}
return ret;
}
};
复杂度分析：
O(n^2)。需要遍历所有的可能组合，计算每个组合的容积，因此时间复杂度为平方级别。O(1)。只使用了常数个变量存储结果和中间值。缺点：
算法思路：
left 和 right 分别指向容器的左右两个端点。left 在最左侧，right 在最右侧。left++。因为固定左边界且继续移动右边界，只会使得容器宽度减小，而高度仍然由左边的短板决定，因此容积只能减小。right--，以尝试找到更高的边界，从而可能获得更大的容积。left 与 right 相遇，整个过程中不断更新最大容积的值。容积公式：
v = (right - left) * min(height[right], height[left])
代码实现：
class Solution {
public:
int maxArea(vector<int>& height) {
int left = 0, right = height.size() - 1, ret = 0;
while (left < right) {
int v = min(height[left], height[right]) * (right - left);
ret = max(ret, v);
// 移动指针
if (height[left] < height[right]) { left++; }
else { right--; }
}
return ret;
}
};
复杂度分析：
O(n)。只需要遍历整个数组一次，两个指针分别从头和尾相向而行。O(1)。只使用了常数个变量存储结果和指针位置。核心思想与证明：
left = 0，right = height.size() - 1，要注意判断数组的长度不能为零，否则无法构成容器。O(n^2)，对于较大的输入会导致超时，适合小规模数据。O(n)，只需线性遍历，适合大规模输入，能够有效解决性能问题。这道题考察了如何通过合理的指针移动来减少不必要的计算，双指针法的精髓在于每次有目的地舍弃一些不可能产生最大值的组合，从而将时间复杂度降至线性。在实际解题时，双指针法是一种非常高效的解法，特别适用于涉及到对区间或边界的遍历优化问题。
通过这两种方法的对比，我们可以看到，暴力法虽然简单，但在性能上存在很大的不足，而通过双指针策略，我们能够有效地减少重复计算，找到问题的最优解。
编写一个算法来判断一个数 n 是不是快乐数。
快乐数定义：
1，或者进入无限循环但始终无法变为 1。1，那么这个数就是快乐数。n 是快乐数就返回 true；否则返回 false。示例 1：
n = 19true19 -> 1^2 + 9^2 = 8282 -> 8^2 + 2^2 = 6868 -> 6^2 + 8^2 = 100100 -> 1^2 + 0^2 + 0^2 = 1示例 2：
n = 2false2 -> 4 -> 16 -> 37 -> 58 -> 89 -> 145 -> 42 -> 20 -> 4 -> 16为了方便叙述，将'对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和'这一操作记为 x 操作。
题目告诉我们，当我们不断重复 x 操作 时，计算一定会进入'死循环'，而'死循环'的方式有两种：
1，即 1 -> 1 -> 1 -> 1...，这是'快乐数'。1。由于上述两种情况只会出现一种，因此，只要我们能确定循环是在'情况一'还是'情况二'，就能判断该数是否是快乐数。
简单证明：
9^2 * 10 = 810（即最大的情况是 9999999999（实际上这道题没有这么大），由鸽巢原理，这个值最终的范围在 [1, 810] 之间）。算法思路：
根据题目分析，我们可以知道，当重复执行 x 操作 时，数值会陷入某种'循环'之中。而快慢指针有一个特性，就是在一个环中，快指针总是会追上慢指针，也就是说它们总会相遇在某个位置上。
1，则这个数是快乐数；1，则这个数不是快乐数。补充知识：如何求一个数 n 每个位置上的数字的平方和：
n 每一位的数字提取出来，使用以下步骤：
int t = n % 10n /= 10n 的值为 0。sum 记录平方和：sum += t * t以下是 C++ 的代码实现，使用快慢指针来解决该问题：
class Solution {
public:
int bitSum(int n) {
// 返回 n 的每一位上的平方和
int sum = 0;
while (n) {
int t = n % 10; // 提取个位
sum += t * t; // 累加平方和
n /= 10; // 去掉个位
}
return sum;
}
bool isHappy(int n) {
int slow = n, fast = bitSum(n);
while (slow != fast) {
// 使用快慢指针，直到二者相遇
slow = bitSum(slow); // 慢指针每次走一步
fast = bitSum(bitSum(fast)); // 快指针每次走两步
}
return slow == 1; // 判断相遇点是否为 1
}
};
bitSum 函数：
n 的每位数字平方和。n 为 0。isHappy 函数：
slow 和 fast，分别为 n 和 bitSum(n)。slow 每次只走一步，而 fast 每次走两步。slow 和 fast 相遇，退出循环。1 上，若是则返回 true，表示为快乐数，否则返回 false。slow 和 fast 相遇时，如果该值为 1，则为快乐数；如果不是 1，则表明进入了其他循环。bitSum 函数时，需要注意提取个位后立即对其平方，并累加到总和中，最后在循环结束后返回结果。O(log n)。在快慢指针法中，求平方和的时间复杂度为对数级。O(1)。没有使用额外的数据结构，只使用了固定数量的变量。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online