【JavaScript】Leetcode每日一题-平方数之和

时间:2022-01-08 02:27:37

【JavaScript】Leetcode每日一题-平方数之和

【题目描述】

给定一个非负整数 c ,你要判断是否存在两个整数 ab,使得 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,继续查找。

有效性证明:

【JavaScript】Leetcode每日一题-平方数之和

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;
}