算法一：枚举 $O(sqrt(c))$

• 枚举 $a$ ，同时用sqrt()求出 $b$ ，在 $a$ 为 $1$ 时，如果$1^2 + b^2 > c$，就不用继续往下枚举b了
• 因为 $c$ 的范围在 [ $0$ , 2^31$ - 1$ ]，所以 $b^2$ 有可能会溢出 $int$，用$long$ 来存

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

算法二：双指针$O(sqrt(c))$

不失一般性，可以假设 $a <= b$。初始时 $a = 0$，$b = sqrt(c)$
可以发现 $b$ 往后走，$a$ 单调往后走，故可以用双指针

1. 如果 $a^2 + b^2 = c$，我们找到了题目要求的一个解，返回 $true$
2. 如果 $a^2 + b^2 < c$，操作$a + 1$
3. 如果 $a^2 + b^2 > c$，操作$b - 1$

class Solution {
    public boolean judgeSquareSum(int c) {
        int l = 0, r = (int)Math.sqrt(c);
        while (l <= r) {
            int sum = l * l + r * r;
            if (sum == c) return true;
            else if (sum < c) l ++;
            else r --;
        }
        return false;
    }
}

算法三：数学

• 由费马定理和可知
  一个非负整数 $c$ 如果能够表示为两个整数的平方和，当且仅当 $c$ 的所有形如 $4k + 3$ 的质因子的幂均为偶数。

• 因此对 c 进行质因数分解，再判断所有形如 4k + 3 的质因子的幂是否均为偶数即可。

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