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

}