🔗 🟡 633. Sum of Square Numbers

tags: `枚舉(Enumeration)` `雙指標(Two Pointers)` `二分搜尋(Binary Search)`

題意

給定一個非負整數 $c$ ，檢查是否存在兩個整數 $a$ 和 $b$ ，使得 $a^2 + b^2 = c$ 。

若存在則返回 $\text{true}$ ，否則返回 $\text{false}$ 。

思路

方法一：枚舉(Enumeration)

如果能夠確定 $a$ 的值，那便可以透過計算 $b = \sqrt{c - a^2}$ 來確定 $b$ 的值。因此，可以從 $a = 0$ 開始枚舉(Enumeration) ，直到 $a^2 \leq c$ 為止，計算 $b$ 的值，檢查是否存在整數解滿足 $a^2 + b^2 = c$ 的條件。

檢查是否滿足條件時，可以檢查 $b$ 是否為整數，也可以透過計算 $a^2 + b^2$ 是否等於 $c$ 來判斷，但前者的計算量較小。

複雜度分析

時間複雜度： $\mathcal{O}(\sqrt{c})$ ，枚舉 $a$ 的範圍為 $[0, \sqrt{c}]$ 。
空間複雜度： $\mathcal{O}(1)$ 。

class Solution:
    def judgeSquareSum(self, c: int) -> bool:
        for x in range(int(c**0.5)+1):
            # 也可以用 double y，然後判斷 y == int(y)
            y = int((c - x**2)**0.5)
            if x ** 2 + y ** 2 == c:
                return True
        return False

class Solution {
public:
    bool judgeSquareSum(int c) {
        for (LL x = 0; x * x <= c; x++){
            double y = sqrt(c - x * x);
            if (y == (int)y){
                return true;
            }
        }
        return false;
    }
};

方法二：雙指標(Two Pointers)

由於 $a, b \isin [0, \sqrt{c}]$ ，可以假設 $a \leq b$ ，並使用雙指針(Two Pointers) 的方法來解決問題。

初始化兩個指標 $a$ 和 $b$ ，分別指向範圍 $[0, \sqrt{c}]$ 的兩端，並根據目前指向的值的平方和與 $c$ 的大小關係調整指針的位置。

如果 $a^2 + b^2 = c$ ，則返回 $\text{true}$ ，表示找到解。
如果 $a^2 + b^2 < c$ ，則表示目前的和太小，需要增加和，移動 $a$ 指針。
如果 $a^2 + b^2 > c$ ，則表示目前的和太大，需要減少和，移動 $b$ 指針。

重複上述步驟，直到 $a > b$ 為止，表示沒有找到解，返回 $\text{false}$ 。

複雜度分析

時間複雜度： $\mathcal{O}(\sqrt{c})$ ，在範圍 $[0, \sqrt{c}]$ 內移動兩個指針。
時間複雜度： $\mathcal{O}(1)$ 。

class Solution:
    def judgeSquareSum(self, c: int) -> bool:
        left, right = 0, int(c**0.5)
        while left <= right:
            cur = left**2 + right**2
            if cur == c:
                return True
            elif cur < c: # 太小
                left += 1
            else: # 太大
                right -= 1
        return False

class Solution {
public:
    bool judgeSquareSum(int c) {
        LL l = 0, r = sqrt(c);
        while (l <= r){
            LL cur = l * l + r * r;
            if (cur == c){
                return true;
            } else if (cur > c){
                r--;
            } else {
                l++;
            }
        }
        return false;
    }
};