跳至主要內容

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


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

🟢   🔖  数学 枚举  🔗 力扣open in new window LeetCodeopen in new window

题目

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整数 三元组 abc

给你一个整数 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. 利用平方数表

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

    • ab 的顺序不影响结果,因此只需枚举 b > a,避免重复。
    • 遍历所有可能的 ab 组合,计算 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数组中不等三元组的数目数组 哈希表 排序🟢🀄️open in new window 🔗open in new window