1925. 统计平方和三元组的数目
1925. 统计平方和三元组的数目
题目
A square triple (a,b,c)
is a triple where a
, b
, and c
are integers and a^2 + b^2 = c^2
.
Given an integer n
, return the number of square triples such that 1 <= a, b, c <= n
.
Example 1:
Input: n = 5
Output: 2
Explanation : The square triples are (3,4,5) and (4,3,5).
Example 2:
Input: n = 10
Output: 4
Explanation : The square triples are (3,4,5), (4,3,5), (6,8,10), and (8,6,10).
Constraints:
1 <= n <= 250
题目大意
一个 平方和三元组 (a,b,c)
指的是满足 a^2 + b^2 = c^2
的 整数 三元组 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
解题思路
利用平方数表:
- 提前计算并存储从
1
到n
的所有平方值,将其存储到一个集合中squares
。 - 这样可以快速检查某个值是否是一个平方数,而无需重复计算。
- 提前计算并存储从
枚举
a
和b
:a
和b
的顺序不影响结果,因此只需枚举b > a
,避免重复。- 遍历所有可能的
a
和b
组合,计算c^2 = a^2 + b^2
。
验证
c
:- 检查
c^2
是否在平方数表中。 - 如果存在,则说明有两个合法的三元组
(a, b, c), (b, a, c)
,计数器加 2。
- 检查
返回结果:
- 累计所有符合条件的三元组数量并返回。
复杂度分析
- 时间复杂度:
O(n^2)
- 构建平方值集合:
O(n)
。 - 枚举
a, b
的组合:O(n^2)
。 - 总复杂度降为
O(n^2)
。
- 构建平方值集合:
- 空间复杂度:
O(n)
,需要存储平方值集合squares
。
代码
/**
* @param {number} n
* @return {number}
*/
var countTriples = function (n) {
let count = 0;
// 预处理平方值
let squares = new Set();
for (let i = 1; i <= n; i++) {
squares.add(i * i);
}
// 枚举 a 和 b,确保 b >= a 避免重复
for (let a = 1; a <= n; a++) {
for (let b = a; b <= n; b++) {
let cSquared = a * a + b * b;
// 检查是否存在 c,使得 c^2 == a^2 + b^2
if (squares.has(cSquared)) {
count += 2;
}
}
}
return count;
};
相关题目
题号 | 标题 | 题解 | 标签 | 难度 | 力扣 |
---|---|---|---|---|---|
2475 | 数组中不等三元组的数目 | 数组 哈希表 排序 | 🟢 | 🀄️ 🔗 |