problem
题意:
solution1:
可以从c的平方根,注意即使c不是平方数,也会返回一个整型数。然后我们判断如果 i*i 等于c,说明c就是个平方数,只要再凑个0,就是两个平方数之和,返回 true;如果不等于的话,那么算出差值 c - i*i,如果这个差值也是平方数的话,返回 true。遍历结束后返回 false,
class Solution {
public:
bool judgeSquareSum(int c) {
for(int i=sqrt(c); i>=; --i)
{
if(i*i == c) return true;
int d = c - i*i, t = sqrt(d);
if(t*t == d) return true;
}
return false;
}
};
solution2:
使用hash set遍历保存至平方根的所有数值的平方,判断是否余值存在即可;
疑问:保存的时候同时进行判断,那么需要判断的余值确定已经在set里了嘛?
class Solution {
public:
bool judgeSquareSum(int c) {
unordered_set<int> sq;//err.
//for(int i=sqrt(c); i>=0; --i)//or...
for(int i=; i<=sqrt(c); ++i)
{
sq.insert(i*i);
if(sq.count(c-i*i)) return true;
}
return false;
}
};
solution3:左右向中间求解,类似于二分法;
疑问:不知道为什么必须使用long类型,否则出错!
class Solution {
public:
bool judgeSquareSum(int c) {
long left = , right = sqrt(c);//err.
while(left<=right)
{
if(left*left + right*right == c) return true;//
else if(left*left+right*right<c) ++left;
else --right;
}
return false;
}
};
solution4:
费马平方和定理 Fermat's theorem on sums of two squares 的一般推广形式:当某个数字的 4k+3 型的质数因子的个数均为偶数时,其可以拆分为两个平方数之和(each prime that is congruent to 3 mod 4 appears with an even exponent in the prime factorization of the number)。那么我们只要统计其质数因子的个数,并且判读,若其为 4k+3 型且出现次数为奇数的话直接返回 false。
参考
1. Leetcode_easy_633. Sum of Square Numbers;
2. Grandyang;
完