leetcode
leetcode 1701 ~ 1750
统计平方和三元组的数目

统计平方和三元组的数目

难度:

标签:

题目描述

代码结果

运行时间: 92 ms, 内存: 16.0 MB


/*
 * Solution using Java Streams to find the number of Pythagorean triplets (a, b, c)
 * where a^2 + b^2 = c^2 and 1 <= a, b, c <= n.
 */
import java.util.stream.IntStream;

public class PythagoreanTripletsStream {
    public long countTriplets(int n) {
        return IntStream.rangeClosed(1, n) // Iterate over a
            .boxed()
            .flatMap(a -> IntStream.rangeClosed(a, n) // Iterate over b, starting from a
                .mapToObj(b -> new int[]{a, b, (int) Math.sqrt(a * b)}) // Calculate c
                .filter(triplet -> triplet[2] <= n && triplet[2] * triplet[2] == triplet[0] * triplet[0] + triplet[1] * triplet[1]) // Check if triplet is valid
            ).count(); // Count valid triplets
    }

    public static void main(String[] args) {
        PythagoreanTripletsStream pts = new PythagoreanTripletsStream();
        System.out.println(pts.countTriplets(5)); // Output: 2
        System.out.println(pts.countTriplets(10)); // Output: 4
    }
}

解释

方法:

The solution uses a set to store the squares of integers from 1 to n. It then iterates through all pairs of integers (i, j) such that 1 <= i < j <= n, and checks if the sum of their squares, i*i + j*j, is present in the set. If it is, it increments the count of triples by 2, considering both (i, j, sqrt(i*i + j*j)) and (j, i, sqrt(i*i + j*j)) as valid triples.

时间复杂度:

O(n^2)

空间复杂度:

O(n)

代码细节讲解

🦆
为什么在遍历平方和时,只需要考虑`1 <= i < j <= n`而不是`1 <= i, j <= n`?这样做有什么优势?
选择`1 <= i < j <= n`是为了避免在计算平方和时重复考虑相同的数字对。例如,对于(i, j)和(j, i),这两个数字对的平方和是相同的,因此只需要计算一次即可。这样做不仅可以减少不必要的计算,还可以避免在最终统计三元组时的重复计数。
🦆
题解中提到,如果`i*i + j*j`在集合中,计数增加2。这种处理方式是否考虑到了所有可能的三元组,还是可能遗漏一些情况?
此处理方式考虑了所有可能的三元组,没有遗漏。因为对于每一对(i, j),如果它们的平方和存在于集合中,表示存在一个k,使得k*k = i*i + j*j。我们通过增加2来计算两种三元组:(i, j, k)和(j, i, k)。因为i和j可以交换位置,故每找到一个有效的平方和,就表示两个有效的三元组配置。
🦆
给定算法在处理平方和时使用了集合来存储平方数,这种数据结构选择对性能的影响如何?是否有更优的数据结构选择?
使用集合存储平方数是一个高效的选择,因为集合(在多数编程语言中)提供了平均常数时间复杂度的成员检查(即查看某个元素是否存在于集合中)。这对于本算法中频繁的检查操作是非常合适的。虽然理论上可以使用其他数据结构如哈希表,但在这种情况下,集合已经提供了必需的功能和效率。
🦆
题解中如果`i*i + j*j`的平方根是整数时才计算为有效的三元组,这里的平方根计算是否会引入额外的计算复杂性?
在题解中,实际上并没有直接计算平方根;而是通过查找集合中是否包含i*i + j*j来间接确定其平方根是否为整数。这种方法避免了直接计算平方根,从而避免了可能的浮点数运算错误和额外的计算复杂性。这是一个更稳定和高效的实现方式。

相关问题