平方数之和

平方数之和,第1张

给定一个非负整数 c ,你要判断是否存在两个整数 a 和 b,使得 a ^ 2 + b ^ 2 = c

提示:0 < = c < = 2 ^ 31 - 1

例如:

输入:c = 5 输出:true

输入:c = 3 输出:false

对于给定的非负整数c,需要判断是否存在两个整数a和b,使得 a ^ 2 + b ^ 2 = c 。当然可以选择枚举所有可能来判断,但是暴力枚举在此题中的时间复杂度会较大。

看到平方,我们可以选择使用sqrt(x)函数,计算x的平方根。只需要在枚举a的同时,令b等于(c-a*a)的平方根,在确定所求得的b是不是整数即可。

由于本题中 0 < = c < = 2 ^ 31 - 1,所以需要避免溢出,使用long型。

C++代码:

class Solution {
public:
    bool judgeSquareSum(int c) {
        for (long a = 0; a * a <= c; a++) {
            double b = sqrt(c - a * a);
            if (b == (int)b) {
                return true;
            }
        }
        return false;
    }
};

JAVA代码:

class Solution {
    public boolean judgeSquareSum(int c) {
        for (long a = 0; a * a <= c; a++) {
            double b = Math.sqrt(c - a * a);
            if (b == (int) b) {
                return true;
            }
        }
        return false;
    }
}

欢迎分享,转载请注明来源:内存溢出

原文地址: https://outofmemory.cn/langs/1498259.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-06-25
下一篇 2022-06-25

发表评论

登录后才能评论

评论列表(0条)

保存