633-sum-of-square-numbers.md

633. 平方数之和 - medium

给定一个非负整数 c ，你要判断是否存在两个整数 a 和 b，使得 a2 + b2 = c 。

 

示例 1：

输入：c = 5
输出：true
解释：1 * 1 + 2 * 2 = 5

示例 2：

输入：c = 3
输出：false

示例 3：

输入：c = 4
输出：true

示例 4：

输入：c = 2
输出：true

示例 5：

输入：c = 1
输出：true

 

提示：

• 0 <= c <= 231 - 1

Solutions

1. 二分搜索

把所有可能的值列举出来，固定一个值 v，然后二分搜索剩下部分，是否存在等于 ns[x] = c - v

时间复杂度为 O(n*log n); 空间复杂度为 O(c ** 0.5)

class Solution:
    def judgeSquareSum(self, c: int) -> bool:
        ns = [i ** 2 for i in range(int(c ** 0.5) + 1)]
        
        n = len(ns)
        x = int((c // 2) ** 0.5) + 1
        for l, v in enumerate(ns):
            r = n - 1
            y = c - v
            while l <= r:
                m = (l + r) // 2
                if ns[m] == y:
                    return True
                if ns[m] < y:
                    l = m + 1
                else:
                    r = m - 1
        
        return False

2. 遍历

遍历 [0, c ** 0.5] 判断 c - i 是否为有平方根

时间复杂度 O(c ** 0.5)；空间复杂度 O(1)

class Solution:
    def judgeSquareSum(self, c: int) -> bool:
        
        i = 0
        while i ** 2 <= c:
            y = (c - i ** 2) ** 0.5
            if y == int(y):
                return True
            i += 1

        return False

3. 双指针

设两个指针，l = 0, r = int(c ** 0.5)，求出 v = l ** 2 + r ** 2

• v == c 返回 True
• v < c 则 l += 1
• v > c 则 r -= 1

当 l > r 时结束

class Solution:
    def judgeSquareSum(self, c: int) -> bool:

        l = 0
        r = int(c ** 0.5)

        while l <= r:
            v = l ** 2 + r ** 2
            if v == c:
                return True
            if v < c:
                l += 1
            else:
                r -= 1
        
        return False