AI毛毛的blog

leetcode打卡-0633平方数之和

题目描述

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

示例:

输入:c = 5

输出:true

解释:1 * 1 + 2 * 2 = 5

解题思路

1. 双指针

如果使用暴力枚举,而且不限定范围,就需要在0~c之间遍历,理论上时间复杂度就成了O(c^2),实在是太高了,所以不太好。

由题目可知,a或b一定会小于√c,所以考虑把a、b两个值作为双指针,从0~√c两头缩放的方式来确定是否满足条件。

  • 两数平方之和sum=c,直接返回True
  • sum < c,a += 1
  • sum > c,b -= 1

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
def judgeSquareSum(self, c: int) -> bool:
left = 0
right = math.isqrt(c)

while left <= right:
res = pow(left, 2) + pow(right, 2)
if res == c:
return True
if res > c:
right -= 1
else:
left += 1

return False

练习一下Rust实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
impl Solution {
pub fn judge_square_sum(c: i32) -> bool {
let mut left: i32 = 0;
let mut right: i32 = (c as f64).sqrt() as i32;
while left <= right {
let s = left.pow(2) + right.pow(2);
match s.cmp(&c) {
std::cmp::Ordering::Less => { left += 1; },
std::cmp::Ordering::Greater => { right -= 1 },
_ => { return true; }
}
}
false
}
}
  • 时间复杂度: O(√c)
  • 空间复杂度: O(1)

总结

这题本来是可以用费马平方和定理来解的,虽然会简化计算,但是那样就变成了一个数学问题,所以还是用双指针的方式来写了。