一個(gè) 平方和三元組 (a,b,c) 指的是滿足 a2 + b2 = c2 的 整數(shù) 三元組 a，b 和 c 。
給你一個(gè)整數(shù) n ，請(qǐng)你返回滿足 1 <= a, b, c <= n 的 平方和三元組 的數(shù)目。
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 遍歷法

由于數(shù)目比較小, 1 <= n <= 250, 可以采用for循環(huán)遍歷方式

n < 5 不存在, 直接報(bào)錯(cuò)(最小: n = 5 即 3, 4, 5)
n > 5, 遍歷 a, b, c 在 3 ~ n范圍內(nèi) (其實(shí)1 ~ n也可以, 只不過多走幾次循環(huán)判斷)
找到滿足a ^ 2 + b ^ 2 = c ^2, 的a, b, c 結(jié)果res + 2
因?yàn)? a, b 可以互換下位置, c最大位置固定, 循環(huán)結(jié)束返回結(jié)果

未翻譯版

    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 }

        // 定義結(jié)果res
        var res = 0

        // 循環(huán) a, 范圍 3 ~ n-1, 其實(shí)如果不做n < 5判斷, 這里從1開始循環(huán)也行
        for a in 3..<n-1 {
         
            // 循環(huán) b, 范圍 a+1 ~ n-1, 這里為什么三者不會(huì)相等, 
            // 其實(shí) 2 * a^2 = c^2, 兩邊開方 c = 根號(hào)2 * a, 根號(hào)2 = 1.414..., 固相等比不滿足
            for b in a+1..<n {
                
                // 循環(huán) a, 范圍 3 ~ n-1, 其實(shí)如果不做n < 5判斷, 這里從1開始循環(huán)也行
                for c in b+1...n {

                    // 如果有 a * a + b * b == c * c 則滿足
                    if a * a + b * b == c * c {
                        // res = res + 2, 因?yàn)閍, b 可以互換位置, C最大位置固定不變, 即2種情況
                        res += 2
                    }
                }
            }
        }
        
        // 返回res
        return res
    }

當(dāng)然我們也可以減少一次循環(huán)

定義c為 a * a + b * b 的開方進(jìn)行判斷

    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 的開方數(shù)`
                let c = Int(sqrt(Double(a * a + b * b)));
                // 這里留意下 c 畢竟是轉(zhuǎn)成double再轉(zhuǎn)int會(huì)有誤差
                // 所以這里要加個(gè) c * c == a * a + b * b判斷
                if c <= n && c * c == a * a + b * b  {
                        res += 2
                }
            }
        }
        
        return res
    }

題目來源：力扣（LeetCode） 感謝力扣爸爸 :)
IOS 算法合集地址