双指针算法实战：快乐数与盛水最多容器
03. 快乐数
题目描述： 编写一个算法来判断一个数 n 是不是快乐数。 「快乐数」定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。然后重复这个过程直到这个数变为 1，也可能是无限循环但始终变不到 1。如果这个过程结果为 1，那么这个数就是快乐数。
思路拆解： 为了方便叙述，我们将「计算各位数字平方和」这一操作记为 x。不断重复 x 操作时，结果只有两种走向：要么收敛到 1，要么陷入死循环。
这里有个关键观察：经过多次变换后，数值范围其实很小（最大不会超过 9^2 * 10 = 810）。根据鸽巢原理，变化过程必然会在有限步内形成循环。既然存在环，我们就可以用「快慢指针」来检测。
核心逻辑：
- 快指针每次走两步，慢指针每次走一步。
- 如果最终相遇在 1，说明是快乐数。
- 如果相遇在其他位置，说明陷入了非 1 的循环，不是快乐数。
辅助函数实现： 我们需要一个函数来计算 n 的各位数字平方和。逻辑很简单：取模提取个位，累加平方，整除去掉个位，循环直到 n 为 0。
class Solution {
public:
// 计算各位数字的平方和
int bitsum(int n) {
int sum = 0;
while (n) {
int t = n % 10;
sum += t * t;
n /= 10;
}
return sum;
}
bool isHappy(int n) {
int slow = n;
int fast = bitsum(n);
// 快慢指针寻找循环点
while (slow != fast) {
slow = bitsum(slow); // 慢指针走一步
fast = bitsum(bitsum(fast)); // 快指针走两步
}
return slow == 1; // 判断相遇点是否为 1
}
};
04. 盛水最多的容器
题目描述： 给定一个长度为 n 的整数数组 height。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i])。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
暴力解法陷阱： 虽然可以用双重循环枚举所有组合，但时间复杂度是 O(n^2)，数据量大时会超时。我们需要更优的策略。
对撞指针策略：
设左右指针 left 和 right 分别指向数组首尾。容器的面积由宽度和较短边的高度决定：
Area = min(height[left], height[right]) * (right - left)
为什么移动短边？ 假设当前左边界小于右边界。此时高度由左边决定。如果我们固定左边，移动右边，宽度减小，且新的高度受限于原来的短边（或更小），面积必然变小。所以，想要获得更大的面积，必须尝试移动那个限制高度的短边，看看能否遇到更高的柱子。
算法流程：
- 初始化左右指针及最大面积变量。
- 当
left < right时循环：- 计算当前面积并更新最大值。
- 比较两边高度，移动较短的一边指针。
- 返回记录的最大面积。
class Solution {
public:
int maxArea(vector<int>& height) {
int left = 0;
int right = height.size() - 1;
int 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^2) 降至 O(n)。掌握这两种模式，能帮你快速解决大量类似的面试题型。
