633. Sum of Square Numbers

 

Given a non-negative integer c, your task is to decide whether there’re two integers a and b such that a2 + b2 = c.

Example 1:

Input: 5
Output: True
Explanation: 1 * 1 + 2 * 2 = 5

 

Example 2:

Input: 3
Output: False

 

这道题让我们求一个数是否能由平方数之和组成,刚开始博主没仔细看题,没有看到必须要是两个平方数之和,博主以为任意一个就可以。所以写了个带优化的递归解法,博主已经不是上来就无脑暴力破解的辣个青葱骚年了,直接带优化。可是居然对 14 返回 false,难道 14 不等于 1+4+9 吗,结果仔细一看,必须要两个平方数之和。好吧,那么递归都省了,直接判断两次就行了。我们可以从c的平方根,注意即使c不是平方数,也会返回一个整型数。然后我们判断如果 ii 等于c,说明c就是个平方数,只要再凑个0,就是两个平方数之和,返回 true;如果不等于的话,那么算出差值 c - ii,如果这个差值也是平方数的话,返回 true。遍历结束后返回 false,参见代码如下:

 

解法一:

class Solution {
public:
    bool judgeSquareSum(int c) {
        for (int i = sqrt(c); i >= 0; --i) {
            if (i * i == c) return true;
            int d = c - i * i, t = sqrt(d);
            if (t * t == d) return true;
        }
        return false;
    }
};

 

下面这种方法用到了 HashSet,从0遍历到c的平方根,对于每个ii,都加入 HashSet 中,然后计算 c - ii,如果这个差值也在 HashSet 中,返回 true,遍历结束返回 false,参见代码如下:

 

解法二:

class Solution {
public:
    bool judgeSquareSum(int c) {
        unordered_set<int> s;
        for (int i = 0; i <= sqrt(c); ++i) {
            s.insert(i * i);
            if (s.count(c - i * i)) return true;
        }
        return false;
    }
};

 

上面两种方法都不是很高效,来看下面这种高效的解法。论坛上有人称之为二分解法,但是博主怎么觉得不是呢,虽然样子很像,但是并没有折半的操作啊。这里用a和b代表了左右两个范围,分别为0和c的平方根,然后 while 循环遍历,如果 aa + bb 刚好等于c,那么返回 true;如果小于c,则a增大1;反之如果大于c,则b自减1,参见代码如下:

 

解法三:

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

 

下面这种解法基于费马平方和定理 Fermat’s theorem on sums of two squares 的一般推广形式:当某个数字的 4k+3 型的质数因子的个数均为偶数时,其可以拆分为两个平方数之和(each prime that is congruent to 3 mod 4 appears with an even exponent in the prime factorization of the number)。那么我们只要统计其质数因子的个数,并且判读,若其为 4k+3 型且出现次数为奇数的话直接返回 false。这里,我们从2开始遍历,若能整除2,则计数器加1,并且c也要除以2。这样我们找到都会是质数因子,因为非质数因子中的因子已经在之前被除掉了,这也是个 trick,需要自己好好想一下。最终在循环退出后,我们还要再判断一下,若剩余的质数因子还是个 4k+3 型,那么返回 false,否则返回 true,参见代码如下:

 

解法四:

class Solution {
public:
    bool judgeSquareSum(int c) {
        for (int i = 2; i * i <= c; ++i) {
            if (c % i != 0) continue;
            int cnt = 0;
            while (c % i == 0) {
                ++cnt;
                c /= i;
            }
            if (i % 4 == 3 && cnt % 2 != 0) return false;
        }
        return c % 4 != 3;
    }
};

 

类似题目:

Valid Perfect Square 

 

参考资料:

https://leetcode.com/problems/sum-of-square-numbers/

https://leetcode.com/problems/sum-of-square-numbers/discuss/104938/simple-c-solution

https://leetcode.com/problems/sum-of-square-numbers/discuss/104930/java-two-pointers-solution

https://leetcode.com/problems/sum-of-square-numbers/discuss/104932/hashset-java-quick-solution-one-for-loop

 

LeetCode All in One 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

×

Help us with donation