sum-of-quare-numbers

Sum of Square Numbers – LeetCode 633

Problem

Description

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

Answer

Original

Code

class Solution {
public:
    bool judgeSquareSum(int c) {
        int upper = static_cast<int>(sqrt(c/2)), test;
        for(int i = 0; i <= upper; ++i){
            test = sqrt(c - i * i);
            if(test * test + i * i == c)
                return true;
        }
        return false;
    }
};

思路

简单的在可行域中枚举。时间复杂度$O(\sqrt{n}log{n})$，空间复杂度$O(1)$。
耗时$4$ ms，排名$27.30\%$

Better

思路

还没看到更好的思路