Leetcode 每日一题练习 ------ 633. 平方数之和

Leetcode 每日一题练习继续讨论:

633. 平方数之和
633. Sum of Square Numbers

题解

本题计算出c的平方根, 用两个变量low和high分别标记0和c的平方根(取下整), 计算两变量的平方和, 若比c大则减小high, 否则增大low, 直到得到平方和为c或者low=high为止.

代码

func judgeSquareSum(c int) bool {
    high := int(math.Sqrt(float64(c)))
    low := 0
    for low <= high{
        if low*low + high*high == c{
            return true
        }else if low*low + high*high > c{
            high--
        }else{
            low++
        }
    }
    return false
}

总结

本题还有一些有趣的相关数学知识, 费马两平方和定理和两数平方和定理, 前者说明了一个奇素数何时能被写为两平方数之和. 满足条件的奇素数也被称为毕达哥拉斯质数, 后者给出了所有大于1的整数在什么情况下能被写为两平方数之和. 是前者的推广. 可参考

2 Likes

刷题佬!

1 Like

大帅哥是真滴快

1 Like

你是真滴快 大帅哥 :grinning: 换头像了又

不许说大帅哥快
要说大帅哥猛

是证件猫猫头这周

Why don’t you write code in c++? Isn’t Python a bit slow for competitive programming.

This is golang language cause I use it daily. And only use C++ for necessary