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

题目

一个 平方和三元组 (a,b,c) 指的是满足 a2 + b2 = c2 的 整数 三元组 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

解答

• 暴力枚举

直接进行枚举即可。

class Solution {
public:
    int countTriples(int n) {
        int cnt = 0;  // 计数器，用于记录满足条件的三元组数量
        for (int a = 1; a <= n; a++) {  // 遍历a的范围从1到n
            for (int b = a + 1; b <= n; b++) {  // 遍历b的范围从a+1到n
                for (int c = b + 1; c <= n; c++) {  // 遍历c的范围从b+1到n
                    if (a * a + b * b == c * c) {  // 检查是否满足勾股定理
                        cnt += 2;  // 满足条件的三元组数量加2
                    }
                }
            }
        }
        return cnt;  // 返回满足条件的三元组数量
    }
};

• 通过固定C降低时间复杂度

暴力枚举法的复杂度为O(n^3)，我们可以对其进行一些优化，比如固定c，只保留a和b的循环。

class Solution {
public:
    int countTriples(int n) {
        int cnt = 0;  // 计数器，用于记录满足条件的三元组数量
        for (int a = 1; a <= n; a++) {  // 遍历a的范围从1到n
            for (int b = a + 1; b <= n; b++) {  // 遍历b的范围从a+1到n
                int c_square = a * a + b * b; //  定义c_square=a*a+b*b
                int c = sqrt(c_square); // 得到整型的变量c，其值为c_square的平方根 
                if (c <= n && c * c == c_square) { // 因为c是被强制转换成int类型进行存储的，所以不仅要判断c是否小于n还要确定c的平方确实等于c_square
                    cnt += 2; // 若符合要求，则cnt+=2 比如（3，4，5）和（4，3，5）只判断一次，但cnt+=2；
                }
            }
        }
        return cnt;  // 返回满足条件的三元组数量
    }
};