【JavaScript】Leetcode每日一题-平方数之和
【题目描述】
给定一个非负整数 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 <= 231 - 1
【分析】
暴力
暴力枚举a,范围\((0,sqrt(c))\)
var judgeSquareSum = function(c) {
for(let i=0;i * i<=c;i++){
if(Math.sqrt(c - i*i) % 1 == 0){
return true;
}
}
return false;
};
双指针
假设 a≤b。初始时 a=0,b= c,进行如下操作:
如果 \(a^2 + b^2 = c\),我们找到了题目要求的一个解,返回 true;
如果 \(a^2 + b^2 < c\),此时需要将 aa 的值加 11,继续查找;
如果 \(a^2 + b^2 > c\),此时需要将 bb 的值减 11,继续查找。
有效性证明:
var judgeSquareSum = function(c) {
let left = 0;
let right = Math.floor(Math.sqrt(c));
while (left <= right) {
const sum = left * left + right * right;
if (sum === c) {
return true;
} else if (sum > c) {
right--;
} else {
left++;
}
}
return false;
};
数学定理 - 费马平方和
费马平方和定理:一个非负整数 cc 如果能够表示为两个整数的平方和,当且仅当 cc 的所有形如 4k + 34k+3 的质因子的幂均为偶数。
var judgeSquareSum = function(c) {
for (let i = 2, cnt = 0; i * i <= c; i++, cnt = 0) {
while (c % i == 0 && ++cnt > 0) c /= i;
if (i % 4 == 3 && cnt % 2 != 0) return false;
}
return c % 4 != 3;
}