LeetCode如何求平方数之和

# LeetCode如何求平方数之和 ## 问题描述 在LeetCode中，平方数之和问题（编号633）的题目要求如下： > 给定一个非负整数 `c`，判断是否存在两个整数 `a` 和 `b`，使得 `a² + b² = c`。如果存在则返回 `true`，否则返回 `false`。 **示例：** - 输入：`c = 5` 输出：`true` 解释：`1² + 2² = 5` - 输入：`c = 3` 输出：`false` 解释：无法找到满足条件的整数组合 ## 解题思路 ### 方法一：暴力枚举（不推荐） 最直观的方法是双重循环枚举所有可能的 `a` 和 `b`，检查是否满足条件。但这种方法的时间复杂度为 `O(c)`，效率较低，不适用于大数。 ```python def judgeSquareSum(c: int) -> bool: for a in range(int(c ** 0.5) + 1): for b in range(int(c ** 0.5) + 1): if a * a + b * b == c: return True return False 

方法二：单指针优化

观察到 a 和 b 的取值范围为 [0, sqrt(c)]，可以固定 a，计算 b = sqrt(c - a²)，然后检查 b 是否为整数。

import math def judgeSquareSum(c: int) -> bool: for a in range(int(math.sqrt(c)) + 1): b = math.sqrt(c - a * a) if b == int(b): return True return False 

时间复杂度：O(sqrt(c))
空间复杂度：O(1)

方法三：双指针法（最优解）

利用双指针从两端向中间逼近： 1. 初始化 left = 0，right = int(sqrt(c))。 2. 计算 sum = left² + right²： - 若 sum == c，返回 true； - 若 sum < c，增加 left； - 若 sum > c，减少 right。 3. 当 left > right 时终止。

import math def judgeSquareSum(c: int) -> bool: left, right = 0, int(math.sqrt(c)) while left <= right: current_sum = left * left + right * right if current_sum == c: return True elif current_sum < c: left += 1 else: right -= 1 return False 

时间复杂度：O(sqrt(c))
空间复杂度：O(1)

方法四：数学法（费马平方和定理）

费马平方和定理指出：

一个自然数 c 可以表示为两个平方数之和，当且仅当在 c 的质因数分解中，所有形如 4k+3 的质因数的幂均为偶数。

利用该定理可以进一步优化： 1. 对 c 进行质因数分解。 2. 检查所有 4k+3 形式的质因数的幂是否为偶数。

import math def judgeSquareSum(c: int) -> bool: for i in range(2, int(math.sqrt(c)) + 1): if c % i == 0: count = 0 while c % i == 0: count += 1 c //= i if i % 4 == 3 and count % 2 != 0: return False return c % 4 != 3 

时间复杂度：O(sqrt(c))（质因数分解耗时）
空间复杂度：O(1)

性能对比

方法	时间复杂度	适用场景
暴力枚举	O©	仅适用于小规模数据
单指针优化	O(sqrt©)	通用，但仍有优化空间
双指针法	O(sqrt©)	最优解，推荐使用
数学法	O(sqrt©)	理论最优，实现较复杂

边界条件与注意事项

1. 输入为0：0 = 0² + 0²，应返回 true。
2. 大数测试：当 c 接近 2^31 - 1 时，需注意整数溢出问题（Python无需担心）。
3. 负数输入：题目已限定 c 为非负整数，无需处理。

总结

平方数之和问题可以通过多种方法解决，其中双指针法在时间复杂度和代码可读性上达到了较好的平衡。对于追求极致性能的场景，可考虑费马平方和定理的数学解法。在实际面试或竞赛中，推荐优先实现双指针法。

提示：LeetCode上的类似问题还包括「有效的完全平方数」（367题），可结合学习。 “`