一个 平方和三元组 (a,b,c) 指的是满足 a2 + b2 = c2 的 整数 三元组 a，b 和 c 。
给你一个整数 n ，请你返回满足 1 <= a, b, c <= n 的 平方和三元组 的数目。
1 <= n <= 250
例子:
输入：n = 5
输出：2
解释：平方和三元组为 (3,4,5) 和 (4,3,5) 。
输入：n = 10
输出：4
解释：平方和三元组为 (3,4,5)，(4,3,5)，(6,8,10) 和 (8,6,10) 。
解题思路
方法1 遍历法
由于数目比较小, 1 <= n <= 250, 可以采用for循环遍历方式
n < 5 不存在, 直接报错(最小: n = 5 即 3, 4, 5)
n > 5, 遍历 a, b, c 在 3 ~ n范围内 (其实1 ~ n也可以, 只不过多走几次循环判断)
找到满足a ^ 2 + b ^ 2 = c ^2, 的a, b, c 结果res + 2
因为: a, b 可以互换下位置, c最大位置固定, 循环结束返回结果
未翻译版
func countTriples(_ n: Int) -> Int {
if n < 5 { return 0 }
var res = 0
for a in 3..<n-1 {
for b in a+1..<n {
for c in b+1...n {
if a * a + b * b == c * c {
res += 2
}
}
}
}
return res
}
翻译版
func countTriples(_ n: Int) -> Int {
// n 小于 5 直接返回0
if n < 5 { return 0 }
// 定义结果res
var res = 0
// 循环 a, 范围 3 ~ n-1, 其实如果不做n < 5判断, 这里从1开始循环也行
for a in 3..<n-1 {
// 循环 b, 范围 a+1 ~ n-1, 这里为什么三者不会相等,
// 其实 2 * a^2 = c^2, 两边开方 c = 根号2 * a, 根号2 = 1.414..., 固相等比不满足
for b in a+1..<n {
// 循环 a, 范围 3 ~ n-1, 其实如果不做n < 5判断, 这里从1开始循环也行
for c in b+1...n {
// 如果有 a * a + b * b == c * c 则满足
if a * a + b * b == c * c {
// res = res + 2, 因为a, b 可以互换位置, C最大位置固定不变, 即2种情况
res += 2
}
}
}
}
// 返回res
return res
}
当然我们也可以减少一次循环
定义c为 a * a + b * b 的开方进行判断
func countTriples(_ n: Int) -> Int {
if n < 5 { return 0 }
var res = 0
for a in 3..<n-1 {
for b in a+1..<n {
// 定义`c`为 `a * a + b * b 的开方数`
let c = Int(sqrt(Double(a * a + b * b)));
// 这里留意下 c 毕竟是转成double再转int会有误差
// 所以这里要加个 c * c == a * a + b * b判断
if c <= n && c * c == a * a + b * b {
res += 2
}
}
}
return res
}
题目来源：力扣（LeetCode） 感谢力扣爸爸 :)
IOS 算法合集地址
网友评论