LeetCode-633.平方数之和

1、题目描述

给定一个非负整数 c ，你要判断是否存在两个整数 a 和 b，使得 a2 + b2 = c 。

示例 1：

输入：c = 5 输出：true 解释：1 * 1 + 2 * 2 = 5

示例 2：

输入：c = 3 输出：false

提示：

0 <= c <= 231 - 1

---

 2、代码： class Solution { public: bool judgeSquareSum(int c) { // 定义两个指针 a 和 b // a 从 0 开始，b 从 sqrt(c) 开始 long a = 0; // 使用 long 防止溢出 long b = static_cast<long>(sqrt(c)); // b 初始化为 c 的平方根 // 双指针法：a 从左向右移动，b 从右向左移动 while (a <= b) { // 计算当前 a^2 + b^2 的值 auto sum = a * a + b * b; if (sum > c) { // 如果 sum 大于 c，说明 b 的值太大了，需要减小 b --b; } else if (sum < c) { // 如果 sum 小于 c，说明 a 的值太小了，需要增大 a ++a; } else { // 如果 sum 等于 c，找到了符合条件的 a 和 b，返回 true return true; } } // 如果循环结束仍未找到符合条件的 a 和 b，返回 false return false; } };

---

3、解题思路

数学性质 ：

如果存在两个整数 a 和 b 满足 a^2 + b^2 = c，那么 a 和 b 的平方值一定在 [0, c] 范围内。因此，我们可以通过枚举一个变量（如 a），并计算另一个变量（如 b）是否满足条件。

双指针法 ：

使用两个指针 a 和 b，分别从 0 和 sqrt(c) 开始移动。计算当前的平方和 sum = a^2 + b^2： 如果 sum == c，说明找到了符合条件的 a 和 b，返回 true。如果 sum < c，说明需要增大 a（即让 a++）。如果 sum > c，说明需要减小 b（即让 b--）。 当 a > b 时，结束循环，返回 false。

时间复杂度 ：

由于 a 和 b 分别从两端向中间移动，最多需要遍历 O(sqrt(c)) 次，因此时间复杂度为 O(sqrt(c))。