給定一個非負整數 c ,你要判斷是否存在兩個整數 a 和 b,使得 a2 + b2 = c 。
示例 1:
輸入:c = 5
輸出:true
解釋:1 * 1 + 2 * 2 = 5
示例 2:
輸入:c = 3
輸出:false
提示:
0 <= c <= 231^{31}31 - 1
相向雙指針,右指針從c\sqrt{c}c?開始,因為大于該值的數的平方已經大于c了,更別說還要加上另一個數:
class Solution {
public:bool judgeSquareSum(int c) {int left = 0;int right = sqrt(c);while (left <= right) {if (left * left < c - right * right) {++left;} else if (left * left > c - right * right) {--right;} else {return true;}}return false;}
};
此算法時間復雜度為O(c\sqrt{c}c?),空間復雜度為O(1)。