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

代码如下：

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实现

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)

总结

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