题目描述
给定一个非负整数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
}
}
|
总结
这题本来是可以用费马平方和定理来解的，虽然会简化计算，但是那样就变成了一个数学问题，所以还是用双指针的方式来写了。