LeetCode 0633.平方数之和：模拟

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

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

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

 

示例 1：

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

示例 2：

输入：c = 3
输出：false

 

提示：

• 0 <= c <= 231 - 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 sqrtclass 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 Truereturn 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
}

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

Tisfy：https://letmefly.blog.csdn.net/article/details/143495591