统计平方和三元组的数目
难度:
标签:
题目描述
代码结果
运行时间: 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`?这样做有什么优势?
▷🦆
题解中提到,如果`i*i + j*j`在集合中,计数增加2。这种处理方式是否考虑到了所有可能的三元组,还是可能遗漏一些情况?
▷🦆
给定算法在处理平方和时使用了集合来存储平方数,这种数据结构选择对性能的影响如何?是否有更优的数据结构选择?
▷🦆
题解中如果`i*i + j*j`的平方根是整数时才计算为有效的三元组,这里的平方根计算是否会引入额外的计算复杂性?
▷