今天更新一道简简单单平方数问题
题目: 给定一个非负整数 c ,你要判断是否存在两个整数 a 和 b,使得 a^2 + b^2 = c。
例如:
c = 5 返回 true, 理由 1^2 + 2^2 = 5
c = 2 返回 true, 理由 1^1 + 1^1 = 2
c = 3 返回 false
解题思路
双指针
设置 a初始为0, b初始为c的最大平方根(因为b是整数, 所以开方之后要取整), 不断收缩找值
1.a^2 + b^2 < c, a增加
2.a^2 + b^2 > c, b减少
直到 a<=b 返回
func judgeSquareSum(_ c: Int) -> Bool {
var a = 0, b = Int(sqrt(Float(c)));
while a <= b {
let sum = a*a + b*b;
if sum < c { a+=1; }
else if sum > c { b-=1; }
else { return true }
}
return false
题目来源:力扣(LeetCode) 感谢力扣爸爸 :)
IOS 算法合集地址
网友评论