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

探索平方和三元组：从问题到 Java 代码实现

在数学与编程的交叉领域，常常会遇到一些有趣且富有挑战性的问题。今天，就让我们深入探讨一下 “平方和三元组” 这个有趣的话题，并使用 Java 语言来实现计算满足特定条件的平方和三元组数量的功能。

一、问题描述:

一个 平方和三元组 (a,b,c) 指的是满足  + =  的 整数 三元组 a，b 和 c 。给你一个整数 n ，请你返回满足 1 <= a, b, c <= n 的 平方和三元组 的数目。

二、什么是平方和三元组:

  平方和三元组是指满足 + =  的整数三元组 a,b和 c。例如,(3,4,5)就是一个著名的平方和三元组，因为+ =9+16= 。

三、代码实现

方法一:暴力解法(三重循环):

public class SquareSumTriples {
    public static int countTriples(int n) {
        //计数器
        int count = 0;
        // 遍历a的取值
        for (int a = 1; a <= n; a++) {
            // 遍历b的取值
            for (int b = 1; b <= n; b++) {
                // 遍历c的取值
                for (int c = 1; c <= n; c++) {
                    // 判断是否满足平方和条件
                    if (a * a + b * b == c * c) {
                        count++;
                    }
                }
            }
        }
        return count;
    }

    //主函数
    public static void main(String[] args) {
        int n = 10;
        //输出
        System.out.println("满足条件的平方和三元组数目为: " + countTriples(n));
    }
}

在上述代码中，countTriples 方法通过三层嵌套的 for 循环，分别对 a，b，c 在  1到 n 的范围内进行遍历。对于每一组 a，b，c 的取值，使用 if 语句判断是否满足   + =   的条件，如果满足，则将计数器 count 加1 。最后，返回 count 的值，即为满足条件的平方和三元组的数目。

这种暴力解法的优点是思路简单直接，易于理解和实现。然而，它的时间复杂度为 ，当 n较大时，计算量会非常庞大，效率较低。

方法二:优化后的解法

为了提高效率，我们可以对上述代码进行优化。观察到对于给定的a  和 b，c 的值是由 a 和 b 决定的，即 。因此，我们可以减少一层循环，通过计算得到 c的值，并判断其是否满足条件。以下是优化后的代码：

public class SquareSumTriplesOptimized {
    public static int countTriples(int n) {
        int count = 0;
        // 遍历a的取值
        for (int a = 1; a <= n; a++) {
            // 遍历b的取值
            for (int b = 1; b <= n; b++) {
                int sumOfSquares = a * a + b * b;
                double cDouble = Math.sqrt(sumOfSquares);
                int c = (int) cDouble;
                // 判断c是否为整数且在范围内
                if (cDouble == c && c >= 1 && c <= n) {
                    count++;
                }
            }
        }
        return count;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("请输入整数n: ");
        int n = scanner.nextInt();
        System.out.println("满足条件的平方和三元组数目为: " + countTriples(n));
        scanner.close();
    }
}

在优化后的代码中，countTriples 方法使用两层嵌套的 for 循环遍历a和b的取值。对于每一组 a 和 b，先计算出它们的平方和 sumOfSquares，然后通过 Math.sqrt 方法计算出平方根 cDouble，并将其转换为整数 c。接着，通过判断 cDouble == c 来确定 c 是否为整数，以及判断 c 是否在1到 n的范围内。如果满足条件，则将计数器 count 加 1。最后，返回 count 的值。

这种优化后的解法时间复杂度为 ,相比暴力解法，效率得到了显著提高。

四、总结

通过对平方和三元组问题的探讨和 Java 代码实现，我们看到了不同解法在效率上的差异。在实际编程中，当面对类似问题时，我们应该思考如何优化算法，以提高程序的性能。暴力解法虽然简单直接，但在处理大规模数据时可能会遇到性能瓶颈。而通过对问题的深入分析，找到其中的规律和优化点，能够帮助我们设计出更高效的算法。希望这篇博客能够帮助读者更好地理解平方和三元组问题以及相关的编程技巧，在数学与编程的学习道路上更进一步。

以上就是关于平方和三元组问题的完整博客内容，你可以根据实际情况进行调整和修改。如果还有其他问题，欢迎随时交流。