day12(力扣)平方数之和(python描述)

梦里梦外; 2021-11-09 23:12 287阅读 0赞

题目描述：给定一个非负整数 c ，你要判断是否存在两个整数 a 和 b，使得 a2 + b2 = c。  
示例1:  
输入: 5  
输出: True  
解释: 1 \* 1 + 2 \* 2 = 5

示例2:  
输入: 3  
输出: False  
分析：该题简单粗暴，我们最先想到的就是暴力循环法求解，但是紧接着一定要意识到的是：**暴力循环法很容易导致时间超出限制**。因此我写出了下列代码（写出来的时候还以为肯定没有问题，感觉都优化到了，然后，看代码吧）：

class Solution:
        def judgeSquareSum(self, c: int) -> bool:
            import math
            i = 0
            j = 0
            b = int(math.sqrt(c)) + 1
            if c == 1 or c == 0:
                return True
            for i in range (b):			#向前行走
                for j in range (b):		#向前行走
                    if i ** 2 + j ** 2 == c:		#判断是否符合题意
                        return True
                while j >= math.sqrt(c) or i >= math.sqrt(c):		#如果有一个已经到平方根点，则退出循环
                    break
            return False

结果显示运行时间还是超出限制了，左思右想，感觉还是问题出在了双重for循环上，心想着突破口只能是在 c 的平方根这里，二者同时从0开始向平方根这里行进的话必然导致循环过多，那么我们能不能一个从前向后走，一个从后向前走，于是代码变成了下面的样子：

class Solution:
        def judgeSquareSum(self, c: int) -> bool:
            import math
            j = 0
            i = int(math.sqrt(c)) 
            while j <= i:
                if i ** 2 + j ** 2 == c:        #相同的话就返回
                    return True
                elif i ** 2 + j ** 2 >= c:      #如果两个平方和太大，则要减小 i 的值
                    i -= 1
                else:                           #否则说明 j 太小
                    j += 1
            return False

算法题的意义，个人认为并不是要你真的记住多少东西，而是你要去理解，并且懂得在很多时候去做优化，不单单是把东西做出来这么简单，我想，算法需要我们的是理解，并加以合理运用，这样，算法的意义才会体现出来。