LeetCode日常-中等-633. 平方数之和

本文最后更新于:2021年5月4日 中午

题目

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

示例 1:

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

示例 2:

1
2
输入:c = 3
输出:false

示例 3:

1
2
输入:c = 4
输出:true

方法一:使用 sqrt 函数

在枚举 a 的同时,使用 sqrt 函数找出 b

1
2
3
4
5
6
class Solution:
def judgeSquareSum(self, c: int) -> bool:
for a in range(int(sqrt(c)) + 1):
if sqrt(c - a**2) % 1 == 0:
return True
return False

复杂度分析

时间复杂度:O(sqrt(c)) 枚举 a 的时间复杂度为 O(sqrt(c)),对于每个 a 的值,可在 O(1) 的时间内寻找 b
空间复杂度:O(1)

方法二:双指针

左右向中间靠拢的双指针

1
2
3
4
5
6
7
8
9
class Solution:
def judgeSquareSum(self, c: int) -> bool:
low, high = 0, int(c**0.5)
while low<=high:
sumOf = low*low+high*high
if sumOf==c: return True
elif sumOf<c: low += 1
else: high -= 1
return False

为什么不会错过答案?

举个例子,c = 18,初始化low = 0,high = 4,那么看如下矩阵:

矩阵沿主对角线对称 low<=high其中的元素表示 low²+high² 的值; 黄色格子表示当前的 low²+high²; 绿色格子表示目标 c; low++相当于让黄色格子下移; high--则相当于让黄色格子左移;
每一列从上到下升序,每一行从左到右升序;
查找的过程具有如下性质:

  1. 初始化时黄色格子必定在矩阵的右上角
  2. 每次比较 low²+high²low 和 c 可以排除矩阵的一行或一列

由于以上性质,当前黄色格子的上方和右边的所有元素一定是已经被排除的,所以黄色格子在搜索过程中只有两种行为:

  • 小于 c :左边的元素都小于当前元素,只能下移,相当于 low++
    此时排除的是黄色格子以及左边同行的元素,都小于 c ,所以不会错过正确答案
  • 大于 c :下面的元素都大于当前元素,只能左移,相当于 high--
    此时排除的是黄色格子以及下方同列的元素,都大于 c ,所以不会错过正确答案

参考:


本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!