一、題目描繪蘇
給定一個非負整數 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
二、題目來源
來源:力扣(LeetCode)
連結:https://leetcode-cn.com/problems/sum-of-square-numbers
三、題解
自己的解法
class Solution {
public boolean judgeSquareSum(int c) {
int a = 0;
int b = (int)Math.sqrt(c);
while(a <= b && a*a + b * b != c){
a++;
b = (int)Math.sqrt(c - a * a);
}
return a<=b;
}
}
官解
方法一:使用 sqrt 函數
class Solution {
public boolean judgeSquareSum(int c) {
for(long a = 0;a * a <= c; a++){
double b = Math.sqrt(c - a*a);
if(b == (int)b)
return true;
}
return false;
}
}
方法二:雙指針法
class Solution {
public:
bool judgeSquareSum(int c) {
long left = 0;
long right = sqrt(c);
while(left <= right){
if(left * left + right * right == c)
return true;
else if(left * left + right * right < c)
left++;
else
right--;
}
return false;
}
};
方法三:數學方法
費馬平方和定理:一個非負整數c如果能夠表示為兩個整數倍的平方和,當且僅當c的所有形如4k + 3的質因子的幂均為偶數
class Solution {
public boolean judgeSquareSum(int c) {
for(long base = 2;base * base <= c; base++){
if(c % base != 0)
continue;
int exp = 0;
while(c % base == 0){
c /= base;
exp++;
}
if (base % 4 == 3 && exp % 2 != 0) {
return false;
}
}
return c % 4 != 3;
}
}