Easy

题目描述

平方和三元组 (a,b,c) 是指满足 a² + b² = c² 的三个整数。

给定一个整数 n，返回满足 1 <= a, b, c <= n 的平方和三元组的数量。

示例 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 <= n <= 250

提示:

  • 遍历所有可能的 (a,b) 对，检查 a² + b² 的平方根是否为不超过 n 的整数
  • 可以使用二分查找或内置的 sqrt 函数来检查一个数的平方根是否为整数

解题思路

解题思路

这是一道寻找勾股数（毕达哥拉斯三元组）的问题。我们需要找到满足 a² + b² = c² 且 1 ≤ a, b, c ≤ n 的所有三元组。

方法一：暴力枚举（推荐）

最直观的方法是枚举所有可能的 a 和 b 值，然后计算 c = √(a² + b²)，检查 c 是否为整数且在范围内。

具体步骤：

  1. 遍历 a 从 1 到 n
  2. 遍历 b 从 1 到 n
  3. 计算 c² = a² + b²
  4. 检查 c 是否为完全平方数且 c ≤ n
  5. 如果满足条件，计数器加 1

时间复杂度为 O(n²)，由于 n ≤ 250，这个复杂度完全可以接受。

方法二：优化枚举

可以通过一些数学性质来优化，比如当 a > b 时，如果 (b,a,c) 已经被计算过，就不需要重复计算 (a,b,c)。但考虑到题目要求统计所有三元组（包括 (3,4,5) 和 (4,3,5) 这样的不同排列），暴力方法更直接。

判断完全平方数可以使用整数平方根函数，然后验证平方根的平方是否等于原数。

代码实现

class Solution {
public:
    int countTriples(int n) {
        int count = 0;
        for (int a = 1; a <= n; a++) {
            for (int b = 1; b <= n; b++) {
                int c_squared = a * a + b * b;
                int c = sqrt(c_squared);
                if (c * c == c_squared && c <= n) {
                    count++;
                }
            }
        }
        return count;
    }
};

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

public class Solution {
    public int CountTriples(int n) {
        int count = 0;
        for (int a = 1; a <= n; a++) {
            for (int b = 1; b <= n; b++) {
                int cSquared = a * a + b * b;
                int c = (int)Math.Sqrt(cSquared);
                if (c * c == cSquared && c <= n) {
                    count++;
                }
            }
        }
        return count;
    }
}

/**
 * @param {number} n
 * @return {number}
 */
var countTriples = function(n) {
    let count = 0;
    
    for (let a = 1; a <= n; a++) {
        for (let b = 1; b <= n; b++) {
            let cSquared = a * a + b * b;
            let c = Math.sqrt(cSquared);
            
            if (c === Math.floor(c) && c <= n) {
                count++;
            }
        }
    }
    
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n²)需要遍历所有可能的 (a,b) 对
空间复杂度O(1)只使用常量额外空间

相关题目