LeetCode如何求平方數之和

# LeetCode如何求平方數之和

## 問題描述

在LeetCode中，平方數之和問題（編號633）的題目要求如下：

> 給定一個非負整數 `c`，判斷是否存在兩個整數 `a` 和 `b`，使得 `a2 + b2 = c`。如果存在則返回 `true`，否則返回 `false`。

**示例：**
- 輸入：`c = 5`  
  輸出：`true`  
  解釋：`12 + 22 = 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 - a2)，然后檢查 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 = left2 + right2： - 若 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 = 02 + 02，應返回 true。
2. 大數測試：當 c 接近 2^31 - 1 時，需注意整數溢出問題（Python無需擔心）。
3. 負數輸入：題目已限定 c 為非負整數，無需處理。

總結

平方數之和問題可以通過多種方法解決，其中雙指針法在時間復雜度和代碼可讀性上達到了較好的平衡。對于追求極致性能的場景，可考慮費馬平方和定理的數學解法。在實際面試或競賽中，推薦優先實現雙指針法。

提示：LeetCode上的類似問題還包括「有效的完全平方數」（367題），可結合學習。 “`