当前位置: 面试刷题>> 判断是否为平方数之和 (经典算法题500道)


题目描述补充

给定一个非负整数 n,判断它是否可以表示为两个整数的平方和。即,是否存在整数 ab,使得 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)),是较为高效的解法。码小课网站上有更多关于算法和数据结构的精彩内容,包括动态规划、图论、搜索算法等,欢迎大家访问学习!

推荐面试题