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)

性能对比

边界条件与注意事项

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

总结

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

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