难度: Easy
一个 平方和三元组 (a,b,c) 指的是满足 a2 + b2 = c2 的 整数 三元组 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运行时间: 92 ms
内存: 16.0 MB
class Solution:
def countTriples(self, n: int) -> int:
cnt=0
s=set([i*i for i in range(1,n+1)])
for i in range(1,n-1):
for j in range(i,n):
if i*i+j*j in s:
cnt+=2
return cnt
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)
class Solution:
def countTriples(self, n: int) -> int:
cnt = 0
s = set([i * i for i in range(1, n + 1)])
for i in range(1, n - 1):
for j in range(i, n):
if i * i + j * j in s:
cnt += 2
return cnt
选择`1 <= i < j <= n`是为了避免在计算平方和时重复考虑相同的数字对。例如，对于(i, j)和(j, i)，这两个数字对的平方和是相同的，因此只需要计算一次即可。这样做不仅可以减少不必要的计算，还可以避免在最终统计三元组时的重复计数。
此处理方式考虑了所有可能的三元组，没有遗漏。因为对于每一对(i, j)，如果它们的平方和存在于集合中，表示存在一个k，使得k*k = i*i + j*j。我们通过增加2来计算两种三元组：(i, j, k)和(j, i, k)。因为i和j可以交换位置，故每找到一个有效的平方和，就表示两个有效的三元组配置。
使用集合存储平方数是一个高效的选择，因为集合（在多数编程语言中）提供了平均常数时间复杂度的成员检查（即查看某个元素是否存在于集合中）。这对于本算法中频繁的检查操作是非常合适的。虽然理论上可以使用其他数据结构如哈希表，但在这种情况下，集合已经提供了必需的功能和效率。
在题解中，实际上并没有直接计算平方根；而是通过查找集合中是否包含i*i + j*j来间接确定其平方根是否为整数。这种方法避免了直接计算平方根，从而避免了可能的浮点数运算错误和额外的计算复杂性。这是一个更稳定和高效的实现方式。