633.平方数之和

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

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

给定一个非负整数 c ,你要判断是否存在两个整数 ab,使得 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++

1
2
3
4
5
6
7
8
9
10
11
12
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

1
2
3
4
5
6
7
8
9
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

1
2
3
4
5
6
7
8
9
10
11
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

1
2
3
4
5
6
7
8
9
10
11
12
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


633.平方数之和
https://blog.letmefly.xyz/2024/11/04/LeetCode 0633.平方数之和/
作者
Tisfy
发布于
2024年11月4日
许可协议