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

🟢   🔖  数学 枚举  🔗 力扣 LeetCode

题目

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. 利用平方数表：

   • 提前计算并存储从 1 到 n 的所有平方值，将其存储到一个集合中 squares。
   • 这样可以快速检查某个值是否是一个平方数，而无需重复计算。

2. 枚举 a 和 b：

   • a 和 b 的顺序不影响结果，因此只需枚举 b > a，避免重复。
   • 遍历所有可能的 a 和 b 组合，计算 c^2 = a^2 + b^2。

3. 验证 c：

   • 检查 c^2 是否在平方数表中。
   • 如果存在，则说明有两个合法的三元组 (a, b, c), (b, a, c)，计数器加 2。

4. 返回结果：

   • 累计所有符合条件的三元组数量并返回。

复杂度分析

• 时间复杂度：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	数组中不等三元组的数目		数组 哈希表 排序	🟢	🀄️ 🔗