1925. 统计平方和三元组的数目

• 标签：数学、枚举
• 难度：简单

题目链接

• 1925. 统计平方和三元组的数目 - 力扣

题目大意

描述：给你一个整数 $n$。

要求：请你返回满足 $1 \le a, b, c \le n$ 的平方和三元组的数目。

说明：

• 平方和三元组：指的是满足 $a^2 + b^2 = c^2$ 的整数三元组 $(a, b, c)$。
• $1 \le n \le 250$。

示例：

• 示例 1：

输入 n = 5
输出 2
解释 平方和三元组为 (3,4,5) 和 (4,3,5)。

• 示例 2：

输入：n = 10
输出：4
解释：平方和三元组为 (3,4,5)，(4,3,5)，(6,8,10) 和 (8,6,10)。

解题思路

思路 1：枚举算法

我们可以在 $[1, n]$ 区间中枚举整数三元组 $(a, b, c)$ 中的 $a$ 和 $b$。然后判断 $a^2 + b^2$ 是否小于等于 $n$，并且是完全平方数。

在遍历枚举的同时，我们维护一个用于统计平方和三元组数目的变量 cnt。如果符合要求，则将计数 cnt 加 $1$。最终，我们返回该数目作为答案。

利用枚举算法统计平方和三元组数目的时间复杂度为 $O(n^2)$。

• 注意：在计算中，为了防止浮点数造成的误差，并且两个相邻的完全平方正数之间的距离一定大于 $1$，所以我们可以用 $\sqrt{a^2 + b^2 + 1}$ 来代替 $\sqrt{a^2 + b^2}$。

思路 1：代码

class Solution:
    def countTriples(self, n: int) -> int:
        cnt = 0
        for a in range(1, n + 1):
            for b in range(1, n + 1):
                c = int(sqrt(a * a + b * b + 1))
                if c <= n and a * a + b * b == c * c:
                    cnt += 1
        return cnt

思路 1：复杂度分析

• 时间复杂度：$O(n^2)$。
• 空间复杂度：$O(1)$。