【Leetcode_easy】633. Sum of Square Numbers

problem

633. Sum of Square Numbers

题意：

solution1:

可以从c的平方根，注意即使c不是平方数，也会返回一个整型数。然后我们判断如果 i*i 等于c，说明c就是个平方数，只要再凑个0，就是两个平方数之和，返回 true；如果不等于的话，那么算出差值 c - i*i，如果这个差值也是平方数的话，返回 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;
    }
};

solution2:

使用hash set遍历保存至平方根的所有数值的平方，判断是否余值存在即可；

疑问：保存的时候同时进行判断，那么需要判断的余值确定已经在set里了嘛？

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

solution3:左右向中间求解，类似于二分法；

疑问：不知道为什么必须使用long类型，否则出错！

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

solution4:

费马平方和定理 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。

参考

1. Leetcode_easy_633. Sum of Square Numbers;

2. Grandyang;

完