633.平方数之和

原题地址

方法一：双指针

Python代码

def judgeSquareSum(self, c: int) -> bool:
    a, b = 0, int(c**0.5)
    while a <= b:
        if a**2 + b**2 == c:
            return True
        elif a**2 + b**2 > c:
            b -= 1
        else:
            a += 1
    return False

时间复杂度O(sqrt(c))

空间复杂度O(1)

方法二：遍历+Python开根号性质

Python中c**0.5得到的是float类型，所以我们可以使用这个性质

def judgeSquareSum(self, c: int) -> bool:
    for a in range(int(c**0.5)+1):
        b = (c-a**2)**0.5
        if b == int(b):
            return True
    return False

时间复杂度O(sqrt(c))

空间复杂度O(1)

方法三：费马平方和定理

一个非负整数 c 能够表示为两个整数的平方和，当且仅当 c 的所有形如 4k+3 的质因子的幂次均为偶数。

也就是非负整数c能表示成多个质数相乘，比如8 = 2*2*2，比如18 = 2*3*3， 这些质数中形如4k+3的那些数，幂次必须为偶数，否则c就不能表示为两个整数的平方和

代码

def judgeSquareSum(self, c: int) -> bool:
    for i in range(2, int(c**0.5) + 1):
        count = 0
        while c % i == 0:
            c /= i
            count += 1
        if i%4 == 3 and count % 2:
            return False
    return c%4 != 3

时间复杂度O(sqrt(c))

空间复杂度O(1)