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

參考