LeetCode 每日一題 633. 平方數之和

633. 平方數之和

給定一個非負整數

c

，你要判斷是否存在兩個整數

a

和

b

，使得 a2 + b2 = c 。

示例 1：

輸入：c = 5
輸出：true
解釋：1 * 1 + 2 * 2 = 5
           

示例 2：

輸入：c = 3
輸出：false
           

示例 3：

輸入：c = 4
輸出：true
           

示例 4：

輸入：c = 2
輸出：true
           

示例 5：

輸入：c = 1
輸出：true
           

提示：

• 0 <= c <= 2^31 - 1

方法一：雙指針

左邊界

left = 0

，右邊界

right = sqrt(c)

。

• 當 left2 + right2 > c，right–；
• 當 left2 + right2 < c，left++；

參考代碼

public boolean judgeSquareSum(int c) {
    int left = 0, right = (int) Math.sqrt(c);
    while (left <= right) {
        int t = left * left + right * right;
        if (t > c) {
            right--;
        } else if (t < c) {
            left++;
        } else {
            return true;
        }
    }
    return false;
}
           

執行結果