肥城房产网_深圳燃气公司电话95158_长沙网站制作推广_百度手机助手app官方下载

🌟快来参与讨论💬，点赞👍、收藏⭐、分享📤，共创活力社区。 🌟

别再犹豫了！快来订阅我们的算法每日双题精讲专栏，一起踏上算法学习的精彩之旅吧！💪

💯前言

💯快乐数

题目描述：

⭐解题思路：

🙋这个解题思路是怎么来的呢？

代码实现（C++为例）：

👀时间复杂度和空间复杂度

💯盛最多水的容器

题目描述：

⭐解题思路：

🙋这个解题思路是怎么来的呢？

代码实现（C++为例）：

👀时间复杂度和空间复杂度

💯总结

💯前言

在算法的奇妙世界里，双指针技巧宛如一把神奇的钥匙，能够开启许多难题的解决之门😎。

今日，就让我们一同深入探究两道借助双指针策略破解的经典题目：快乐数与盛最多水的容器。

📣由于俩道题目均为数组，这里的双指针算法指的是：利用数组下标代替指针

当我们遇到，数组分块，数组划分的问题时，可以考虑使用双指针法。

💯快乐数

题目链接👉【力扣】

题目描述：

编写一个算法来判断一个数 n 是否为 “快乐数”。

“快乐数” 定义为：

对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，
然后重复这个过程直到这个数变为 1，也可能是无限循环但始终变不到 1。
如果这个过程结果为 1，那么这个数就是快乐数。

示例：

输入：n = 19
输出：true
解释：
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1

⭐解题思路：

我们可以使用双指针法来解决这个问题。定义一个快指针 fast 和一个慢指针 slow，初始时都指向数字 n。快指针每次计算下一个数时，会连续计算两次平方和，而慢指针每次只计算一次。通过不断重复这个过程，如果快指针等于 1，说明该数是快乐数；如果快指针等于慢指针且不等于 1，说明进入了循环，该数不是快乐数。

🙋这个解题思路是怎么来的呢？

我们进行画图：

我们发现该题目像极了，环问题，因此我们的解题思路为快慢指针。

代码实现（C++为例）：

class Solution {
public:// 计算整数 n 各个数位上数字的平方和int sumN(int n) {int sum = 0;// 循环计算每个数位上数字的平方和while (n!= 0) {int t = n % 10;  // 取出 n 的最后一位数字sum += t * t;    // 将该数字的平方累加到 sum 中n = n / 10;      // 去掉 n 的最后一位数字}return sum;}// 判断整数 n 是否为快乐数bool isHappy(int n) {int slow = n;    // 慢指针，初始值为输入的整数 nint fast = sumN(n);  // 快指针，初始值为 n 的各个数位数字平方和// 使用快慢指针法检测是否存在循环while (slow!= fast) {slow = sumN(slow);   // 慢指针每次移动一步fast = sumN(sumN(fast));  // 快指针每次移动两步}return slow == 1;   // 如果慢指针等于 1，则说明 n 是快乐数}
};

👀时间复杂度和空间复杂度

时间复杂度：

计算单个数字的数位平方和的时间复杂度为 $O(logn)$ ，因为数字的位数与 $logn$ 成正比。
在 isHappy 函数中，使用快慢指针法来判断是否为快乐数，在没有循环的情况下，时间复杂度取决于达到 1 的步数，最多不会超过 $O(logn)$ 。如果存在循环，时间复杂度也不会超过 $O(logn)$ ，因为每次计算数位平方和都会使数字减小，最终会收敛到一个较小的范围。

空间复杂度：

代码中只使用了有限的几个变量，不随输入规模增长，所以空间复杂度为 $O(1)$ 。