Java Program to Find Pythagorean Triplets in an Array

2025 年 3 月 28 日 | 阅读 10 分钟

勾股数是一个由三个正整数 (a, b, c) 组成的集合，它们满足以下方程

在这个方程中，'c' 是最大的数，代表直角三角形的斜边，而 'a' 和 'b' 是另外两条边。例如，集合 (3, 4, 5) 构成一个勾股数，因为当你将 3 和 4 的平方相加时 (3² + 4²)，你得到 5 的平方 (即 9 + 16 = 25)。

示例 1

输入

输出

 
False

朴素方法

代码中使用的朴素方法涉及三个嵌套循环来检查数组中每个可能的三个元素组合，并检查它们的平方是否满足勾股定理。这种方法虽然直接，但由于其立方时间复杂度，对于大型数组效率低下。

算法

步骤 1： 遍历数组并对每个元素进行平方。

步骤 2： 将平方后的值按非递减顺序排列。

步骤 3： 从排序数组中的最大元素开始向后迭代。

步骤 4： 将当前元素视为斜边，并使用双指针方法检查数组中的另外两个元素是否加起来等于该值。

步骤 5： 如果找到一个勾股数，则返回 true。如果经过所有检查后没有找到勾股数，则返回 false。

实施

文件名：PythagoreanTripletChecker.java

import java.io.*; 
// Class for finding Pythagorean triplets within an array
class PythagoreanTripletChecker {
    // Method to verify if the array contains any Pythagorean triplet
    static boolean hasPythagoreanTriplet(int[] numbers, int size) {
        // Iterate over each element in the array
        for (int i = 0; i < size; i++) {
            // Iterate over the subsequent elements after the first element
            for (int j = i + 1; j < size; j++) {
                // Iterate over the elements after the jth element
                for (int k = j + 1; k < size; k++) {
                    // Compute the squares of the three selected elements
                    int square1 = numbers[i] * numbers[i];
                    int square2 = numbers[j] * numbers[j];
                    int square3 = numbers[k] * numbers[k];
                    // Check if any combination of these squares satisfies the Pythagorean theorem
                    // square1 is the hypotenuse
                    if (square1 == square2 + square3 ||
                        // square2 is the hypotenuse
                        square2 == square1 + square3 ||
                        // square3 is the hypotenuse
                        square3 == square1 + square2) {
                        return true; // Pythagorean triplet found
                    }
                }
            }
        }
        // If no triplet is found after all iterations, return false
        return false;
    }
    // Main Method to run the program and test the hasPythagoreanTriplet Function
    public static void main(String[] args) {
        // Initialize an array with some example values
        int[] array = {3, 1, 4, 6, 5};
        // Get the length of the array
        int length = array.length;
        // Call the Method to check for Pythagorean triplets and print the result
        if (hasPythagoreanTriplet(array, length)) {
            System.out.println("Yes"); // Print "Yes" if a triplet is found
        } else {
            System.out.println("No");  // Print "No" if no triplet is found
        }
    }
}   

输出

Yes

时间复杂度： 由于三个嵌套循环，时间复杂度为 O(n^3)。

辅助空间复杂度： 辅助空间复杂度为 O(1)，因为只使用了少数几个额外的变量。

使用排序方法

“使用排序”方法涉及对数组进行排序，使元素按可预测的顺序排列，从而简化了问题。通过将双指针方法等技术应用于排序后的数组，可以有效地检查诸如勾股数之类的条件。

算法

步骤 1： 遍历数组并将每个元素转换为其平方值。

步骤 2： 将这些平方值按升序排列。

步骤 3： 对于每个元素（潜在的斜边），使用双指针技术

初始化两个指针：一个指向数组的开头，另一个指向当前元素的前一个位置。
检查两个指针处值的和是否等于当前元素。

步骤 4： 根据和的比较调整指针

如果和小于当前元素，则将左指针向右移动。
如果和大于当前元素，则将右指针向左移动。

步骤 5： 如果发现一个满足勾股定理的有效勾股数，则返回 true。如果在检查了所有组合后没有找到这样的勾股数，则返回 false。

实施

文件名：TripletChecker.java

import java.util.Arrays;
class TripletChecker {
    // Checks if the array contains a Pythagorean triplet
    static boolean containsPythagoreanTriplet(int[] numbers, int size) {
        // Compute the Square of each element in the array
        for (int i = 0; i < size; i++) {
            numbers[i] = numbers[i] * numbers[i];
        }
        // Sort the array with squared values
        Arrays.sort(numbers);
        // Check for Pythagorean triplets by fixing one element and using two pointers for the other two
        for (int i = size - 1; i >= 2; i--) {
            int left = 0; // Start pointer
            int right = i - 1; // End pointer
            while (left < right) {
                // Check if the sum of the two pointers equals the current element
                if (numbers[left] + numbers[right] == numbers[i]) {
                    return true; // Triplet found
                }
                // Move the pointers based on the sum comparison
                if (numbers[left] + numbers[right] < numbers[i]) {
                    left++;
                } else {
                    right--;
                }
            }
        }
        // No triplet found
        return false;
    }
    // Main Method to run the program and test the containsPythagoreanTriplet Function
    public static void main(String[] args) {
        int[] array = {3, 1, 4, 6, 5}; // Example array
        int size = array.length;
        // Test for Pythagorean triplet and print result
        if (containsPythagoreanTriplet(array, size)) {
            System.out.println("Yes"); // Triplet exists
        } else {
            System.out.println("No"); // Triplet does not exist
        }
    }
}   

输出

Yes

时间复杂度： O(n^2) 主要由双指针搜索勾股数决定。

辅助空间： O(1) 除输入数组和指针外，没有额外的空间。

方法：使用哈希

哈希可以加快查找勾股数的过程，通过使用频率数组来快速检查潜在的勾股数元素是否存在。该方法最大限度地减少了对嵌套循环和重复比较的需求。

算法

步骤 1： 确定数组中的最大值，以确定频率数组所需的尺寸。

步骤 2： 构建一个频率数组，其中每个索引对应一个数字，并保存该数字在原始数组中的计数。

步骤 3： 对于频率数组中的每个潜在值，仅当该值存在时才继续。

步骤 4： 对于 b 的每个可能值，如果 b 不存在或 a 和 b 相同但 a 只出现一次，则跳过。

步骤 5： 将 c 计算为 a^2 + b^2 的平方根，并检查 c 是否存在于频率数组中并满足勾股条件。如果找到一个有效的勾股数，则返回 true；否则，在所有检查完成后返回 false。

实施

文件名：TripletFinder.java

import java.util.*;
class TripletFinder {
    // Function to check for the existence of a Pythagorean triplet in an array
    static boolean findPythagoreanTriplet(int[] numbers, int length) {
        int maxValue = 0;
        // Determine the maximum value in the array
        for (int i = 0; i < length; i++) {
            maxValue = Math.max(maxValue, numbers[i]);
        }
        // Create a frequency array to store occurrences of each number
        int[] frequency = new int[maxValue + 1];
        // Populate the frequency array
        for (int i = 0; i < length; i++) {
            frequency[numbers[i]]++;
        }
        // Check for each possible value of 'a'
        for (int a = 1; a <= maxValue; a++) {
            // Skip if 'a' is not present in the array
            if (frequency[a] == 0) continue;
            // Check for each possible value of 'b'
            for (int b = 1; b <= maxValue; b++) {
                // Skip if 'b' is not present or 'a' and 'b' are the same but 'a' appears only once
                if ((a == b && frequency[a] == 1) || frequency[b] == 0) continue;
                // Calculate 'c' as the square root of (a^2 + b^2)
                int c = (int) Math.sqrt(a * a + b * b);
                // Check if c^2 is equal to (a^2 + b^2) and 'c' is a valid number
                if (c * c == a * a + b * b && c <= maxValue && frequency[c] > 0) {
                    return true; // Triplet found
                }
            }
        }
        // No Pythagorean triplet found
        return false;
    }
    // Main Method to test the findPythagoreanTriplet Function
    public static void main(String[] args) {
        int[] numbers = {3, 2, 4, 6, 5, 5}; // Example array
        int length = numbers.length;
        // Test and print whether a Pythagorean triplet is present
        if (findPythagoreanTriplet(numbers, length)) {
            System.out.println("Yes"); // Triplet exists
        } else {
            System.out.println("No"); // Triplet does not exist
        }
    }
}   

输出

Yes

时间复杂度： O(n²)，其中 n 是数组中的元素数量。这是由于用于查找有效勾股数的嵌套循环。

辅助空间复杂度： O(n)，用于管理数组的频率映射。

方法：暴力法结合哈希表优化

代码使用一种暴力方法来检查每对元素以找到勾股数。为了提高效率，它利用 HashMap，该方法可以快速验证潜在的斜边是否存在于勾股数中。

算法

步骤 1： 初始化一个 HashMap 来记录数组中每个数字的频率。

步骤 2： 遍历数组，用每个数字的计数更新 HashMap。

步骤 3： 对于数组中的每一对元素，使用勾股关系计算潜在的斜边。

步骤 4： 检查计算出的斜边是否存在于 HashMap 中，并确保其平方等于两个元素的平方和。

步骤 5： 如果在此过程中找到了有效的勾股数，则返回 true。如果在检查所有组合后未发现此类勾股数，则返回 false。

实施

文件名： TripletDetector.java

import java.util.HashMap;
class TripletDetector {
    // Function to check if any Pythagorean triplet is present in the array
    static boolean containsPythagoreanTriplet(int[] numbers, int length) {
        // Create a HashMap to store the frequency of each element
        HashMap<Integer, Integer> frequencyMap = new HashMap<>();
        // Populate the HashMap with the frequency of each element
        for (int i = 0; i < length; i++) {
            frequencyMap.put(numbers[i], frequencyMap.getOrDefault(numbers[i], 0) + 1);
        }
        // Examine every pair of elements to determine if they could be part of a Pythagorean triplet
        for (int i = 0; i < length - 1; i++) {
            for (int j = i + 1; j < length; j++) {
                // Compute the possible hypotenuse based on the two chosen numbers
                int hypotenuse = (int) Math.sqrt(numbers[i] * numbers[i] + numbers[j] * numbers[j]);
                // Confirm if the squared value of this hypotenuse matches the sum of the squares of the two chosen numbers
                // and check if the hypotenuse is present in the frequency map
                if (hypotenuse * hypotenuse == numbers[i] * numbers[i] + numbers[j] * numbers[j] &&
                    frequencyMap.containsKey(hypotenuse) &&
                    frequencyMap.get(hypotenuse) > 0) {
                    return true; // Triplet found
                }
            }
        }
        // No Pythagorean triplet found
        return false;
    }
    // Main Method to test the containsPythagoreanTriplet Function
    public static void main(String[] args) {
        int[] numbers = {3, 2, 4, 6, 5}; // Example array
        int length = numbers.length;
        // Test and print whether a Pythagorean triplet exists in the array
        if (containsPythagoreanTriplet(numbers, length)) {
            System.out.println("Yes"); // Triplet exists
        } else {
            System.out.println("No"); // Triplet does not exist
        }
    }
}   

输出

Yes

时间复杂度： O(n^2)，由于嵌套循环检查元素对。

空间复杂度： O(n)，用于存储元素频率的 HashMap。

方法：使用排序和哈希集

排序和哈希集方法首先对数组的平方值进行排序，以便于系统地检查勾股数。然后，它使用 HashSet 来有效地检查当前平方值与任何先前遇到的平方值的差值是否构成有效的勾股数。

算法

步骤 1： 计算数组中每个元素的平方，并将这些平方值按升序排序。

步骤 2： 从排序列表的末尾开始，将每个值视为潜在的斜边。

步骤 3： 使用 HashSet 来记住先前遇到的平方值，并确定对于每个潜在的斜边是否可以形成一个有效的勾股数。

步骤 4： 如果找到一个有效的勾股数，则返回 true；否则，在检查完所有可能性后返回 false。

实施

文件名：TripletFinder.java

import java.util.Arrays;
import java.util.HashSet;
public class TripletFinder {
    //Function to determine if there is a Pythagorean triplet in the array
    static boolean containsPythagoreanTriplet(int[] numbers, int size) {
        //Square each element in the array
        for (int i = 0; i < size; i++) {
            numbers[i] = numbers[i] * numbers[i];
        }
        // Sort the squared values
        Arrays.sort(numbers);
        // Check for each element from the end of the sorted array
        for (int i = size - 1; i > 1; i--) {
            HashSet<Integer> seenSquares = new HashSet<>();
            // Check for pairs of earlier elements that can form a Pythagorean triplet with the current element
            for (int j = i - 1; j >= 0; j--) {
                // Verify if the difference between the current squared value and the earlier squared value is present in the set
                if (seenSquares.contains(numbers[i] - numbers[j])) {
                    return true; // Pythagorean triplet found
                }
                // Add the current squared value to the set
                seenSquares.add(numbers[j]);
            }
        }
        // No Pythagorean triplet found
        return false;
    }
    // Main Method to test the containsPythagoreanTriplet Function
    public static void main(String[] args) {
        int[] numbers = {3, 2, 4, 6, 5}; // Example array
        int size = numbers.length;
        // Check and print if a Pythagorean triplet is present
        if (containsPythagoreanTriplet(numbers, size)) {
            System.out.println("Yes"); // Triplet exists
        } else {
            System.out.println("No"); // Triplet does not exist
        }
    }
}   

输出

Yes

时间复杂度： O(n^2)，由于嵌套循环检查元素对。

辅助空间复杂度： O(n)，用于跟踪已见平方值的 HashSet。

下一个主题Java 中的字符流类

Java Program to Find Pythagorean Triplets in an Array

朴素方法

算法

实施

使用排序方法

算法

实施

方法：使用哈希

算法

实施

方法：暴力法结合哈希表优化

算法

实施

方法：使用排序和哈希集

算法

实施

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Java Conversion

Java Misc

Java Program to Find Pythagorean Triplets in an Array

朴素方法

算法

实施

使用排序方法

算法

实施

方法：使用哈希

算法

实施

方法：暴力法结合哈希表优化

算法

实施

方法：使用排序和哈希集

算法

实施

相关帖子

nth Prime Number Java

Java 的 Kalangs 是谁

Java 中的 java.util.LongSummaryStatistics 类及示例

Java Top 10 Libraries

Java 中的 HttpEntity

Java 中的图像处理 - 改变图像方向

extends Keyword in Java

Java 中从第一个节点到最后一个节点的受限路径数量

Why String is Immutable or Final in Java

Partition Number in Java

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器