LeetCode 633 : Sum of Square Numbers（python）

原題：

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

Example 1:

Input: 5

Output: True

Explanation: 1 * 1 + 2 * 2 = 5

Example 2:

Input: 3

Output: False

思路：

題目大意就是求一個非負整數能否拆解成兩個整數的平方之和，由于int類型的範圍 -2147483648～2147483647，是以可以預感到如果是o(n)的複雜度的算法（代碼一），而且又是python寫的，逾時的可能性極大！如果是把問題轉換成判斷c-a^2是否是一個平方數，則可以把複雜度降為o(n^0.5)，詳見代碼二。

代碼一：o(n)，逾時！

class Solution:
    def judgeSquareSum(self, c):
        """
        :type c: int
        :rtype: bool
        """
        for i in range(,int(c**)+):
            for j in range(,int(c**)+):
                if((i**+j**)>c):
                    break
                elif((i**+j**)==c):
                    return True
        return False
           

代碼二：o(n^0.5)，通過！

class Solution:
    def judgeSquareSum(self, c):
        """
        :type c: int
        :rtype: bool
        """
        for i in range(,int(c**)+):
            j=c-i**
            if((int(j**)**)==j):
                return True
        return False