当前位置：首页 > article >正文

LeetCode 0633.平方数之和：模拟

article 2024/11/5 2:30:39

【LetMeFly】633.平方数之和：模拟

力扣题目链接：https://leetcode.cn/problems/sum-of-square-numbers/

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

示例 1：

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

示例 2：

输入：c = 3
输出：false

提示：

0 <= c <= 2³¹ - 1

解题方法：模拟

从 $0$ 到 $\sqrt{c}$ 模拟 $a$ ，令 $b=int(\sqrt{c-a^2})$ 。如果 $a^2+b^2=c$ 则返回true。

时间复杂度 $O(\sqrt{c})$
空间复杂度 $O (1)$

AC代码

C++

class Solution {
public:
    bool judgeSquareSum(int c) {
        for (int a = sqrt(c); a >= 0; a--) {
            int b = sqrt(c - a * a);
            if (b * b + a * a == c) {
                return true;
            }
        }
        return false;
    }
};

Python

from math import sqrt

class Solution:
    def judgeSquareSum(self, c: int) -> bool:
        for a in range(int(sqrt(c)) + 1):
            b = sqrt(c - a * a)
            if b == int(b):
                return True
        return False

Java

class Solution {
    public boolean judgeSquareSum(int c) {
        for (int a = (int)Math.sqrt(c); a >= 0; a--) {
            int b = (int)Math.sqrt(c - a * a);
            if (a * a + b * b == c) {
                return true;
            }
        }
        return false;
    }
}

Go

package main
import "math"

func judgeSquareSum(c int) bool {
    for a := int(math.Sqrt(float64(c))); a >= 0; a-- {
        b := int(math.Sqrt(float64(c - a * a)))
        if a * a + b * b == c {
            return true
        }
    }
    return false
}