leetcode
leetcode 551 ~ 600
平方数之和

平方数之和

难度:

标签:

题目描述

代码结果

运行时间: 48 ms, 内存: 16.6 MB


/*
 * 思路:
 * 通过Java Stream生成一个从0到sqrt(c)的整数流
 * 检查是否存在一对整数a和b满足a^2 + b^2 = c
 */
import java.util.stream.IntStream;
 
public class Solution {
    public boolean judgeSquareSum(int c) {
        return IntStream.rangeClosed(0, (int) Math.sqrt(c))
                        .anyMatch(a -> {
                            int b = (int) Math.sqrt(c - a * a);
                            return a * a + b * b == c;
                        });
    }
}

解释

方法:

该题解是基于数论知识和费马平方和定理来解决问题的。它首先判断特殊情况,如果c为0,则直接返回True。然后对c进行预处理,将c中的所有2的因子除尽。接下来,利用费马平方和定理的一个推论:一个正整数如果是4k+3的形式,那么它不能表示为两个整数的平方和。如果c满足这种情况,则直接返回False。最后,通过枚举c的因子,检查是否存在奇数次的因子为4k+3的形式,如果存在则返回False,否则返回True。

时间复杂度:

O(sqrt(c) * log c)

空间复杂度:

O(1)

代码细节讲解

🦆
题解中提到`将c中的所有2的因子除尽`,请问这一步骤在解决问题中起到了什么作用?
在处理平方数之和的问题时,去除2的因子是为了简化问题。根据费马平方和定理,一个数如果可以表示为两个整数的平方和,那么它的每个因子也同样可以表示为两个整数的平方和。数字2可以被表示为1^2 + 1^2,因此任何包含因子2的数可以简化去除这些2的因子,不影响最终结果。这样做可以减少后续处理的复杂度,只需关注剩余部分是否可以表示为两个整数的平方和。
🦆
为什么在判断是否能表示为两整数的平方和时,需要检查c是否为`4k+3`的形式?
这个判断基于费马平方和定理的一个重要推论。具体来说,如果一个正整数可以表示为两个整数的平方和,那么它在质因子分解后,形式为4k+3的质因子(如果有的话)必须出现偶数次。如果一个数本身是4k+3的形式(其中k是整数),并且不能进一步分解为其它质因子的乘积,那么这个数就不能表示为两个整数的平方和。因此,这一步是针对不能进一步分解的情况进行快速判断。
🦆
题解中使用了`费马平方和定理`,能否详细解释这个定理及其对解题的具体影响?
费马平方和定理指出,一个正整数可以表示为两个整数的平方和(即n = a^2 + b^2)的条件是:它的每一个形式为4k+3的素数因子的指数都是偶数。这个定理对解题有直接影响,因为它提供了一个判断数是否可以表示为两个整数的平方和的数学基础。通过这个定理,我们可以通过检查数的质因子分解来确定是否满足条件,从而避免了盲目的搜索或过于复杂的运算。
🦆
在枚举c的因子时,为什么选择从3开始,步长为4进行枚举?这种枚举策略有什么特别的意义吗?
选择从3开始,步长为4进行枚举是因为我们特别关注形式为4k+3的因子。这是因为,根据费马平方和定理,形式为4k+3的素数因子在质因子分解中必须具有偶数次幂才能使该数表示为两个整数的平方和。当从3开始以4为步长枚举时,你会得到3, 7, 11, 15, ..., 这确保了每个枚举的数都是形式为4k+3的数,从而直接定位到可能的关键因子,提高了效率。

相关问题

有效的完全平方数

给你一个正整数 num 。如果 num 是一个完全平方数,则返回 true ,否则返回 false

完全平方数 是一个可以写成某个整数的平方的整数。换句话说,它可以写成某个整数和自身的乘积。

不能使用任何内置的库函数,如  sqrt

 

示例 1:

输入:num = 16
输出:true
解释:返回 true ,因为 4 * 4 = 16 且 4 是一个整数。

示例 2:

输入:num = 14
输出:false
解释:返回 false ,因为 3.742 * 3.742 = 14 但 3.742 不是一个整数。

 

提示:

  • 1 <= num <= 231 - 1