【题目】

给定非负整数c，本题的任务是判断是否存在整数a和b，使得a²+b²=c。

Example 1:

Input: 5
Output: True
Explanation: 1 * 1 + 2 * 2 = 5

 

Example 2:

 

Input: 3
Output: False

【解法】暴力破解
列出所有a和b的和，并与c比较。a和b的值在（0，sqrt(c)）之间。
参考解法（Java版本）也是超过了时间限制。

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

Time limited

• Time complexity : O(c)O(c)O(c). Two loops upto c\sqrt{c}c​. Here, ccc refers to the given integer(sum of squares).

• Space complexity : O(1)O(1)O(1). Constant extra space is used.

【解法】暴力破解优化版

待续

【解法】

class Solution:
    def judgeSquareSum(self, c):
        """
        :type c: int
        :rtype: bool
        """
        sq = set()
        count = int(math.sqrt(c))
        # use (count + 1) because first index is 0
        for i in range(count + 1):
            sq.add(i ** 2)

        for n in sq:
            if c - n in sq:
                return True

        return False

Runtime: 284 ms, faster than 46.56% of Python3 online submissions for Sum of Square Numbers. Memory Usage: 17.6 MB, less than 13.04% of Python3 online submissions for Sum of Square Numbers. 优化

class Solution:
    def judgeSquareSum(self, c: int) -> bool:
        """
        :type c: int
        :rtype: bool
        """
        sq = set()
        count = int(math.sqrt(c))
        # use (count + 1) because first index is 0
        for i in range(count + 1):
            a2  = i ** 2
            sq.add(a2)
            if c - a2 in sq:
                return True
        return False

Runtime: 276 ms, faster than 50.81% of Python3 online submissions for Sum of Square Numbers. Memory Usage: 17.7 MB, less than 5.19% of Python3 online submissions for Sum of Square Numbers. 【解法】two pointers

class Solution:
    def judgeSquareSum(self, c: int) -> bool:
        cc = int(c ** 0.5)
        left = 0
        right = cc
        while left <= right:
            res = left ** 2 + right ** 2
            if res == c:
                return True
            elif res < c:
                left += 1
            elif res > c:
                right -= 1
        return False

Runtime: 272 ms, faster than 52.35% of Python3 online submissions for Sum of Square Numbers. Memory Usage: 13.9 MB, less than 46.37% of Python3 online submissions for Sum of Square Numbers.

Time complexity : O(\sqrt(c))
Space complexity: O(1)
Note that 0 can be one of the factorization numbers and two integers could be equal.