leetcode平方数之和（python3）

题目描述：

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

示例1:

输入: 5
输出: True
解释: 1 * 1 + 2 * 2 = 5

示例2:

输入: 3
输出: False


代码实现：
方法一：
解题思路：双指针，判断并不断调整a,b的值

时间复杂度：先计算最大a值，然后计算b值，后进行微调。接近O(a + b) 。
只用了两个变量，空间复杂度：O(1)。

 1 class Solution(object):
 2     def judgeSquareSum(self, c):
 3         """
 4         :type c: int
 5         :rtype: bool
 6         """
 7         a=0
 8         while  c-a*a >=0:
 9             a += 1  
10         b=0 
11         while a>=b:    
12             if b*b == c-(a-1)*(a-1):
13                 return  True
14             elif b*b < c-(a-1)*(a-1):
15                 b += 1
16             else :
17                 a -=1

方法二：

解题思路：双指针，计算a,b的取值范围，求平方和

最多遍历到sqrt(c), 时间复杂度：O(sqrt(c))。
只用了两个变量，空间复杂度：O(1)。

 1 class Solution(object):
 2     def judgeSquareSum(self, c):
 3         """
 4         :type c: int
 5         :rtype: bool
 6         """
 7         a=0
 8         b = int(math.sqrt(c))
 9         while a <=b:
10             if (a*a +b*b)==c:
11                 return True
12             elif (a*a +b*b)>c:
13                 b -=1
14             else:
15                 a +=1

上面两个方法大同小异，方法一是算出a的最大取值，方法二是借助math.sqrt(c)计算取值范围。方法2的执行时间更短。

方法三：二分查找（耗时较长）它是一种效率较高的查找方法。（二分查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。）

具体实现中，为防止算术溢出，一般采 ⌊low+(high-low)/2⌋ $代替。$

$二分查找的时间复杂度为O(logn)，但是在此段代码中，外层还嵌套了遍历列表，所以时间复杂度为O(alogn)$

 1 class Solution(object):
 2     def judgeSquareSum(self, c):
 3         """
 4         :type c: int
 5         :rtype: bool
 6         """
 7         a=0
 8         arange =[]
 9         while  c-a*a >=0:
10             arange.append(a*a)
11             a += 1        
12         for n in arange:
13             low = 0
14             high = len(arange)-1
15             while low < high:
16                 mid = (low+high)//2   #向下取整
17                 if arange[mid] == c-n:
18                     return True
19                 elif arange[mid] > c-n:
20                     high = mid
21                 else:
22                     low = mid+1
23             if arange[low]==c-n:
24                 return True    
25         return False

leetcode平方数之和（python3）

推荐阅读