题目描述补充:
给定一个非负整数 n
,判断它是否可以表示为两个整数的平方和。即,是否存在整数 a
和 b
,使得 a^2 + b^2 = n
。如果存在,则返回 true
;否则,返回 false
。
示例 1:
输入: n = 5
输出: true
解释: 2^2 + 1^2 = 5
示例 2:
输入: n = 3
输出: false
PHP 示例代码:
function isSquareSum($n) {
$max = (int)sqrt($n); // 找到最大的可能平方根
for ($a = 0; $a <= $max; $a++) {
$b = sqrt($n - $a * $a); // 计算对应的b的平方根
if ($b == (int)$b) { // 检查b是否为整数
return true;
}
}
return false;
}
// 测试示例
echo isSquareSum(5) ? "true" : "false"; // 输出: true
echo "\n";
echo isSquareSum(3) ? "true" : "false"; // 输出: false
Python 示例代码:
def isSquareSum(n):
max_square = int(n ** 0.5)
for a in range(max_square + 1):
b_square = n - a ** 2
if b_square >= 0 and b_square ** 0.5 == int(b_square ** 0.5):
return True
return False
# 测试示例
print(isSquareSum(5)) # 输出: True
print(isSquareSum(3)) # 输出: False
JavaScript 示例代码:
function isSquareSum(n) {
let max = Math.floor(Math.sqrt(n));
for (let a = 0; a <= max; a++) {
let b = Math.sqrt(n - a * a);
if (b === Math.floor(b)) {
return true;
}
}
return false;
}
// 测试示例
console.log(isSquareSum(5)); // 输出: true
console.log(isSquareSum(3)); // 输出: false
码小课分享:
在解决这类问题时,理解数学原理是关键。上述代码通过遍历可能的平方数 a^2
,并计算剩余的数 n - a^2
是否为完全平方数来判断是否满足条件。这种方法的时间复杂度为 O(sqrt(n)),是较为高效的解法。码小课网站上有更多关于算法和数据结构的精彩内容,包括动态规划、图论、搜索算法等,欢迎大家访问学习!